// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/builtins/builtins-collections-gen.h"

#include "src/builtins/builtins-constructor-gen.h"
#include "src/builtins/builtins-iterator-gen.h"
#include "src/builtins/builtins-utils-gen.h"
#include "src/code-stub-assembler.h"
#include "src/heap/factory-inl.h"
#include "src/heap/heap-inl.h"
#include "src/objects/hash-table-inl.h"
#include "src/objects/js-collection.h"
#include "src/objects/ordered-hash-table.h"
#include "torque-generated/builtins-base-from-dsl-gen.h"
#include "torque-generated/builtins-collections-from-dsl-gen.h"

#include "src/objects/ordered-hash-table-inl.h" // weolar

namespace v8 {
namespace internal {

    using compiler::Node;
    template <class T>
    using TNode = compiler::TNode<T>;
    template <class T>
    using TVariable = compiler::TypedCodeAssemblerVariable<T>;

    class BaseCollectionsAssembler : public CodeStubAssembler,
                                     public CollectionsBuiltinsFromDSLAssembler {
    public:
        explicit BaseCollectionsAssembler(compiler::CodeAssemblerState* state)
            : CodeStubAssembler(state)
            , CollectionsBuiltinsFromDSLAssembler(state)
        {
        }

        virtual ~BaseCollectionsAssembler() = default;

    protected:
        enum Variant { kMap,
            kSet,
            kWeakMap,
            kWeakSet };

        // Adds an entry to a collection.  For Maps, properly handles extracting the
        // key and value from the entry (see LoadKeyValue()).
        void AddConstructorEntry(Variant variant, TNode<Context> context,
            TNode<Object> collection, TNode<Object> add_function,
            TNode<Object> key_value,
            Label* if_may_have_side_effects = nullptr,
            Label* if_exception = nullptr,
            TVariable<Object>* var_exception = nullptr);

        // Adds constructor entries to a collection.  Choosing a fast path when
        // possible.
        void AddConstructorEntries(Variant variant, TNode<Context> context,
            TNode<Context> native_context,
            TNode<Object> collection,
            TNode<Object> initial_entries);

        // Fast path for adding constructor entries.  Assumes the entries are a fast
        // JS array (see CodeStubAssembler::BranchIfFastJSArray()).
        void AddConstructorEntriesFromFastJSArray(Variant variant,
            TNode<Context> context,
            TNode<Context> native_context,
            TNode<Object> collection,
            TNode<JSArray> fast_jsarray,
            Label* if_may_have_side_effects);

        // Adds constructor entries to a collection using the iterator protocol.
        void AddConstructorEntriesFromIterable(Variant variant,
            TNode<Context> context,
            TNode<Context> native_context,
            TNode<Object> collection,
            TNode<Object> iterable);

        // Constructs a collection instance. Choosing a fast path when possible.
        TNode<Object> AllocateJSCollection(TNode<Context> context,
            TNode<JSFunction> constructor,
            TNode<Object> new_target);

        // Fast path for constructing a collection instance if the constructor
        // function has not been modified.
        TNode<Object> AllocateJSCollectionFast(TNode<HeapObject> constructor);

        // Fallback for constructing a collection instance if the constructor function
        // has been modified.
        TNode<Object> AllocateJSCollectionSlow(TNode<Context> context,
            TNode<JSFunction> constructor,
            TNode<Object> new_target);

        // Allocates the backing store for a collection.
        virtual TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
            TNode<IntPtrT> at_least_space_for)
            = 0;

        // Main entry point for a collection constructor builtin.
        void GenerateConstructor(Variant variant,
            Handle<String> constructor_function_name,
            TNode<Object> new_target, TNode<IntPtrT> argc,
            TNode<Context> context);

        // Retrieves the collection function that adds an entry. `set` for Maps and
        // `add` for Sets.
        TNode<Object> GetAddFunction(Variant variant, TNode<Context> context,
            TNode<Object> collection);

        // Retrieves the collection constructor function.
        TNode<JSFunction> GetConstructor(Variant variant,
            TNode<Context> native_context);

        // Retrieves the initial collection function that adds an entry. Should only
        // be called when it is certain that a collection prototype's map hasn't been
        // changed.
        TNode<JSFunction> GetInitialAddFunction(Variant variant,
            TNode<Context> native_context);

        // Checks whether {collection}'s initial add/set function has been modified
        // (depending on {variant}, loaded from {native_context}).
        void GotoIfInitialAddFunctionModified(Variant variant,
            TNode<Context> native_context,
            TNode<Object> collection,
            Label* if_modified);

        // Gets root index for the name of the add/set function.
        RootIndex GetAddFunctionNameIndex(Variant variant);

        // Retrieves the offset to access the backing table from the collection.
        int GetTableOffset(Variant variant);

        // Estimates the number of entries the collection will have after adding the
        // entries passed in the constructor. AllocateTable() can use this to avoid
        // the time of growing/rehashing when adding the constructor entries.
        TNode<IntPtrT> EstimatedInitialSize(TNode<Object> initial_entries,
            TNode<BoolT> is_fast_jsarray);

        void GotoIfNotJSReceiver(Node* const obj, Label* if_not_receiver);

        // Determines whether the collection's prototype has been modified.
        TNode<BoolT> HasInitialCollectionPrototype(Variant variant,
            TNode<Context> native_context,
            TNode<Object> collection);

        // Gets the initial prototype map for given collection {variant}.
        TNode<Map> GetInitialCollectionPrototype(Variant variant,
            TNode<Context> native_context);

        // Loads an element from a fixed array.  If the element is the hole, returns
        // `undefined`.
        TNode<Object> LoadAndNormalizeFixedArrayElement(TNode<FixedArray> elements,
            TNode<IntPtrT> index);

        // Loads an element from a fixed double array.  If the element is the hole,
        // returns `undefined`.
        TNode<Object> LoadAndNormalizeFixedDoubleArrayElement(
            TNode<HeapObject> elements, TNode<IntPtrT> index);
    };

    void BaseCollectionsAssembler::AddConstructorEntry(
        Variant variant, TNode<Context> context, TNode<Object> collection,
        TNode<Object> add_function, TNode<Object> key_value,
        Label* if_may_have_side_effects, Label* if_exception,
        TVariable<Object>* var_exception)
    {
        compiler::CodeAssemblerScopedExceptionHandler handler(this, if_exception,
            var_exception);
        CSA_ASSERT(this, Word32BinaryNot(IsTheHole(key_value)));
        if (variant == kMap || variant == kWeakMap) {
            BaseBuiltinsFromDSLAssembler::KeyValuePair pair = if_may_have_side_effects != nullptr
                ? LoadKeyValuePairNoSideEffects(context, key_value,
                    if_may_have_side_effects)
                : LoadKeyValuePair(context, key_value);
            Node* key_n = pair.key;
            Node* value_n = pair.value;
            CallJS(CodeFactory::Call(isolate()), context, add_function, collection,
                key_n, value_n);
        } else {
            DCHECK(variant == kSet || variant == kWeakSet);
            CallJS(CodeFactory::Call(isolate()), context, add_function, collection,
                key_value);
        }
    }

    void BaseCollectionsAssembler::AddConstructorEntries(
        Variant variant, TNode<Context> context, TNode<Context> native_context,
        TNode<Object> collection, TNode<Object> initial_entries)
    {
        TVARIABLE(BoolT, use_fast_loop,
            IsFastJSArrayWithNoCustomIteration(context, initial_entries));
        TNode<IntPtrT> at_least_space_for = EstimatedInitialSize(initial_entries, use_fast_loop.value());
        Label allocate_table(this, &use_fast_loop), exit(this), fast_loop(this),
            slow_loop(this, Label::kDeferred);
        Goto(&allocate_table);
        BIND(&allocate_table);
        {
            TNode<Object> table = AllocateTable(variant, context, at_least_space_for);
            StoreObjectField(collection, GetTableOffset(variant), table);
            GotoIf(IsNullOrUndefined(initial_entries), &exit);
            GotoIfInitialAddFunctionModified(variant, native_context, collection,
                &slow_loop);
            Branch(use_fast_loop.value(), &fast_loop, &slow_loop);
        }
        BIND(&fast_loop);
        {
            TNode<JSArray> initial_entries_jsarray = UncheckedCast<JSArray>(initial_entries);
#if DEBUG
            CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(context, initial_entries_jsarray));
            TNode<Map> original_initial_entries_map = LoadMap(initial_entries_jsarray);
#endif

            Label if_may_have_side_effects(this, Label::kDeferred);
            AddConstructorEntriesFromFastJSArray(variant, context, native_context,
                collection, initial_entries_jsarray,
                &if_may_have_side_effects);
            Goto(&exit);

            if (variant == kMap || variant == kWeakMap) {
                BIND(&if_may_have_side_effects);
#if DEBUG
                {
                    // Check that add/set function has not been modified.
                    Label if_not_modified(this), if_modified(this);
                    GotoIfInitialAddFunctionModified(variant, native_context, collection,
                        &if_modified);
                    Goto(&if_not_modified);
                    BIND(&if_modified);
                    Unreachable();
                    BIND(&if_not_modified);
                }
                CSA_ASSERT(this, WordEqual(original_initial_entries_map, LoadMap(initial_entries_jsarray)));
#endif
                use_fast_loop = Int32FalseConstant();
                Goto(&allocate_table);
            }
        }
        BIND(&slow_loop);
        {
            AddConstructorEntriesFromIterable(variant, context, native_context,
                collection, initial_entries);
            Goto(&exit);
        }
        BIND(&exit);
    }

    void BaseCollectionsAssembler::AddConstructorEntriesFromFastJSArray(
        Variant variant, TNode<Context> context, TNode<Context> native_context,
        TNode<Object> collection, TNode<JSArray> fast_jsarray,
        Label* if_may_have_side_effects)
    {
        TNode<FixedArrayBase> elements = LoadElements(fast_jsarray);
        TNode<Int32T> elements_kind = LoadElementsKind(fast_jsarray);
        TNode<JSFunction> add_func = GetInitialAddFunction(variant, native_context);
        CSA_ASSERT(
            this,
            WordEqual(GetAddFunction(variant, native_context, collection), add_func));
        CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(context, fast_jsarray));
        TNode<IntPtrT> length = SmiUntag(LoadFastJSArrayLength(fast_jsarray));
        CSA_ASSERT(this, IntPtrGreaterThanOrEqual(length, IntPtrConstant(0)));
        CSA_ASSERT(
            this, HasInitialCollectionPrototype(variant, native_context, collection));

#if DEBUG
        TNode<Map> original_collection_map = LoadMap(CAST(collection));
        TNode<Map> original_fast_js_array_map = LoadMap(fast_jsarray);
#endif
        Label exit(this), if_doubles(this), if_smiorobjects(this);
        GotoIf(IntPtrEqual(length, IntPtrConstant(0)), &exit);
        Branch(IsFastSmiOrTaggedElementsKind(elements_kind), &if_smiorobjects,
            &if_doubles);
        BIND(&if_smiorobjects);
        {
            auto set_entry = [&](Node* index) {
                TNode<Object> element = LoadAndNormalizeFixedArrayElement(
                    CAST(elements), UncheckedCast<IntPtrT>(index));
                AddConstructorEntry(variant, context, collection, add_func, element,
                    if_may_have_side_effects);
            };

            // Instead of using the slower iteration protocol to iterate over the
            // elements, a fast loop is used.  This assumes that adding an element
            // to the collection does not call user code that could mutate the elements
            // or collection.
            BuildFastLoop(IntPtrConstant(0), length, set_entry, 1,
                ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
            Goto(&exit);
        }
        BIND(&if_doubles);
        {
            // A Map constructor requires entries to be arrays (ex. [key, value]),
            // so a FixedDoubleArray can never succeed.
            if (variant == kMap || variant == kWeakMap) {
                CSA_ASSERT(this, IntPtrGreaterThan(length, IntPtrConstant(0)));
                TNode<Object> element = LoadAndNormalizeFixedDoubleArrayElement(elements, IntPtrConstant(0));
                ThrowTypeError(context, MessageTemplate::kIteratorValueNotAnObject,
                    element);
            } else {
                DCHECK(variant == kSet || variant == kWeakSet);
                auto set_entry = [&](Node* index) {
                    TNode<Object> entry = LoadAndNormalizeFixedDoubleArrayElement(
                        elements, UncheckedCast<IntPtrT>(index));
                    AddConstructorEntry(variant, context, collection, add_func, entry);
                };
                BuildFastLoop(IntPtrConstant(0), length, set_entry, 1,
                    ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
                Goto(&exit);
            }
        }
        BIND(&exit);
#if DEBUG
        CSA_ASSERT(this,
            WordEqual(original_collection_map, LoadMap(CAST(collection))));
        CSA_ASSERT(this,
            WordEqual(original_fast_js_array_map, LoadMap(fast_jsarray)));
#endif
    }

    void BaseCollectionsAssembler::AddConstructorEntriesFromIterable(
        Variant variant, TNode<Context> context, TNode<Context> native_context,
        TNode<Object> collection, TNode<Object> iterable)
    {
        Label exit(this), loop(this), if_exception(this, Label::kDeferred);
        CSA_ASSERT(this, Word32BinaryNot(IsNullOrUndefined(iterable)));

        TNode<Object> add_func = GetAddFunction(variant, context, collection);
        IteratorBuiltinsAssembler iterator_assembler(this->state());
        IteratorBuiltinsAssembler::IteratorRecord iterator = iterator_assembler.GetIterator(context, iterable);

        CSA_ASSERT(this, Word32BinaryNot(IsUndefined(iterator.object)));

        TNode<Object> fast_iterator_result_map = LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX);
        TVARIABLE(Object, var_exception);

        Goto(&loop);
        BIND(&loop);
        {
            TNode<Object> next = iterator_assembler.IteratorStep(
                context, iterator, &exit, fast_iterator_result_map);
            TNode<Object> next_value = CAST(iterator_assembler.IteratorValue(
                context, next, fast_iterator_result_map));
            AddConstructorEntry(variant, context, collection, add_func, next_value,
                nullptr, &if_exception, &var_exception);
            Goto(&loop);
        }
        BIND(&if_exception);
        {
            iterator_assembler.IteratorCloseOnException(context, iterator,
                var_exception.value());
        }
        BIND(&exit);
    }

    RootIndex BaseCollectionsAssembler::GetAddFunctionNameIndex(Variant variant)
    {
        switch (variant) {
        case kMap:
        case kWeakMap:
            return RootIndex::kset_string;
        case kSet:
        case kWeakSet:
            return RootIndex::kadd_string;
        }
        UNREACHABLE();
    }

    void BaseCollectionsAssembler::GotoIfInitialAddFunctionModified(
        Variant variant, TNode<Context> native_context, TNode<Object> collection,
        Label* if_modified)
    {
        STATIC_ASSERT(JSCollection::kAddFunctionDescriptorIndex == JSWeakCollection::kAddFunctionDescriptorIndex);
        GotoIfInitialPrototypePropertyModified(
            LoadMap(CAST(collection)),
            GetInitialCollectionPrototype(variant, native_context),
            JSCollection::kAddFunctionDescriptorIndex,
            GetAddFunctionNameIndex(variant), if_modified);
    }

    TNode<Object> BaseCollectionsAssembler::AllocateJSCollection(
        TNode<Context> context, TNode<JSFunction> constructor,
        TNode<Object> new_target)
    {
        TNode<BoolT> is_target_unmodified = WordEqual(constructor, new_target);

        return Select<Object>(
            is_target_unmodified,
            [=] { return AllocateJSCollectionFast(constructor); },
            [=] {
                return AllocateJSCollectionSlow(context, constructor,
                    new_target);
            });
    }

    TNode<Object> BaseCollectionsAssembler::AllocateJSCollectionFast(
        TNode<HeapObject> constructor)
    {
        CSA_ASSERT(this, IsConstructorMap(LoadMap(constructor)));
        TNode<Object> initial_map = LoadObjectField(constructor, JSFunction::kPrototypeOrInitialMapOffset);
        return CAST(AllocateJSObjectFromMap(initial_map));
    }

    TNode<Object> BaseCollectionsAssembler::AllocateJSCollectionSlow(
        TNode<Context> context, TNode<JSFunction> constructor,
        TNode<Object> new_target)
    {
        ConstructorBuiltinsAssembler constructor_assembler(this->state());
        return CAST(constructor_assembler.EmitFastNewObject(context, constructor,
            new_target));
    }

    void BaseCollectionsAssembler::GenerateConstructor(
        Variant variant, Handle<String> constructor_function_name,
        TNode<Object> new_target, TNode<IntPtrT> argc, TNode<Context> context)
    {
        const int kIterableArg = 0;
        CodeStubArguments args(this, argc);
        TNode<Object> iterable = args.GetOptionalArgumentValue(kIterableArg);

        Label if_undefined(this, Label::kDeferred);
        GotoIf(IsUndefined(new_target), &if_undefined);

        TNode<Context> native_context = LoadNativeContext(context);
        TNode<Object> collection = AllocateJSCollection(
            context, GetConstructor(variant, native_context), new_target);

        AddConstructorEntries(variant, context, native_context, collection, iterable);
        Return(collection);

        BIND(&if_undefined);
        ThrowTypeError(context, MessageTemplate::kConstructorNotFunction,
            HeapConstant(constructor_function_name));
    }

    TNode<Object> BaseCollectionsAssembler::GetAddFunction(
        Variant variant, TNode<Context> context, TNode<Object> collection)
    {
        Handle<String> add_func_name = (variant == kMap || variant == kWeakMap)
            ? isolate()->factory()->set_string()
            : isolate()->factory()->add_string();
        TNode<Object> add_func = GetProperty(context, collection, add_func_name);

        Label exit(this), if_notcallable(this, Label::kDeferred);
        GotoIf(TaggedIsSmi(add_func), &if_notcallable);
        GotoIfNot(IsCallable(CAST(add_func)), &if_notcallable);
        Goto(&exit);

        BIND(&if_notcallable);
        ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, add_func,
            HeapConstant(add_func_name), collection);

        BIND(&exit);
        return add_func;
    }

    TNode<JSFunction> BaseCollectionsAssembler::GetConstructor(
        Variant variant, TNode<Context> native_context)
    {
        int index;
        switch (variant) {
        case kMap:
            index = Context::JS_MAP_FUN_INDEX;
            break;
        case kSet:
            index = Context::JS_SET_FUN_INDEX;
            break;
        case kWeakMap:
            index = Context::JS_WEAK_MAP_FUN_INDEX;
            break;
        case kWeakSet:
            index = Context::JS_WEAK_SET_FUN_INDEX;
            break;
        }
        return CAST(LoadContextElement(native_context, index));
    }

    TNode<JSFunction> BaseCollectionsAssembler::GetInitialAddFunction(
        Variant variant, TNode<Context> native_context)
    {
        int index;
        switch (variant) {
        case kMap:
            index = Context::MAP_SET_INDEX;
            break;
        case kSet:
            index = Context::SET_ADD_INDEX;
            break;
        case kWeakMap:
            index = Context::WEAKMAP_SET_INDEX;
            break;
        case kWeakSet:
            index = Context::WEAKSET_ADD_INDEX;
            break;
        }
        return CAST(LoadContextElement(native_context, index));
    }

    int BaseCollectionsAssembler::GetTableOffset(Variant variant)
    {
        switch (variant) {
        case kMap:
            return JSMap::kTableOffset;
        case kSet:
            return JSSet::kTableOffset;
        case kWeakMap:
            return JSWeakMap::kTableOffset;
        case kWeakSet:
            return JSWeakSet::kTableOffset;
        }
        UNREACHABLE();
    }

    TNode<IntPtrT> BaseCollectionsAssembler::EstimatedInitialSize(
        TNode<Object> initial_entries, TNode<BoolT> is_fast_jsarray)
    {
        return Select<IntPtrT>(
            is_fast_jsarray,
            [=] { return SmiUntag(LoadFastJSArrayLength(CAST(initial_entries))); },
            [=] { return IntPtrConstant(0); });
    }

    void BaseCollectionsAssembler::GotoIfNotJSReceiver(Node* const obj,
        Label* if_not_receiver)
    {
        GotoIf(TaggedIsSmi(obj), if_not_receiver);
        GotoIfNot(IsJSReceiver(obj), if_not_receiver);
    }

    TNode<Map> BaseCollectionsAssembler::GetInitialCollectionPrototype(
        Variant variant, TNode<Context> native_context)
    {
        int initial_prototype_index;
        switch (variant) {
        case kMap:
            initial_prototype_index = Context::INITIAL_MAP_PROTOTYPE_MAP_INDEX;
            break;
        case kSet:
            initial_prototype_index = Context::INITIAL_SET_PROTOTYPE_MAP_INDEX;
            break;
        case kWeakMap:
            initial_prototype_index = Context::INITIAL_WEAKMAP_PROTOTYPE_MAP_INDEX;
            break;
        case kWeakSet:
            initial_prototype_index = Context::INITIAL_WEAKSET_PROTOTYPE_MAP_INDEX;
            break;
        }
        return CAST(LoadContextElement(native_context, initial_prototype_index));
    }

    TNode<BoolT> BaseCollectionsAssembler::HasInitialCollectionPrototype(
        Variant variant, TNode<Context> native_context, TNode<Object> collection)
    {
        TNode<Map> collection_proto_map = LoadMap(LoadMapPrototype(LoadMap(CAST(collection))));

        return WordEqual(collection_proto_map,
            GetInitialCollectionPrototype(variant, native_context));
    }

    TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedArrayElement(
        TNode<FixedArray> elements, TNode<IntPtrT> index)
    {
        TNode<Object> element = UnsafeLoadFixedArrayElement(elements, index);
        return Select<Object>(
            IsTheHole(element), [=] { return UndefinedConstant(); },
            [=] { return element; });
    }

    TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedDoubleArrayElement(
        TNode<HeapObject> elements, TNode<IntPtrT> index)
    {
        TVARIABLE(Object, entry);
        Label if_hole(this, Label::kDeferred), next(this);
        TNode<Float64T> element = LoadFixedDoubleArrayElement(CAST(elements), index, MachineType::Float64(),
            0, INTPTR_PARAMETERS, &if_hole);
        { // not hole
            entry = AllocateHeapNumberWithValue(element);
            Goto(&next);
        }
        BIND(&if_hole);
        {
            entry = UndefinedConstant();
            Goto(&next);
        }
        BIND(&next);
        return entry.value();
    }

    class CollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
    public:
        explicit CollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
            : BaseCollectionsAssembler(state)
        {
        }

        // Check whether |iterable| is a JS_MAP_KEY_ITERATOR_TYPE or
        // JS_MAP_VALUE_ITERATOR_TYPE object that is not partially consumed and still
        // has original iteration behavior.
        void BranchIfIterableWithOriginalKeyOrValueMapIterator(TNode<Object> iterable,
            TNode<Context> context,
            Label* if_true,
            Label* if_false);

        // Check whether |iterable| is a JS_SET_TYPE or JS_SET_VALUE_ITERATOR_TYPE
        // object that still has original iteration behavior. In case of the iterator,
        // the iterator also must not have been partially consumed.
        void BranchIfIterableWithOriginalValueSetIterator(TNode<Object> iterable,
            TNode<Context> context,
            Label* if_true,
            Label* if_false);

    protected:
        template <typename IteratorType>
        Node* AllocateJSCollectionIterator(Node* context, int map_index,
            Node* collection);
        TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
            TNode<IntPtrT> at_least_space_for) override;
        Node* GetHash(Node* const key);
        Node* CallGetHashRaw(Node* const key);
        Node* CallGetOrCreateHashRaw(Node* const key);

        // Transitions the iterator to the non obsolete backing store.
        // This is a NOP if the [table] is not obsolete.
        typedef std::function<void(Node* const table, Node* const index)>
            UpdateInTransition;
        template <typename TableType>
        std::pair<TNode<TableType>, TNode<IntPtrT>> Transition(
            TNode<TableType> const table, TNode<IntPtrT> const index,
            UpdateInTransition const& update_in_transition);
        template <typename IteratorType, typename TableType>
        std::pair<TNode<TableType>, TNode<IntPtrT>> TransitionAndUpdate(
            TNode<IteratorType> const iterator);
        template <typename TableType>
        std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>> NextSkipHoles(
            TNode<TableType> table, TNode<IntPtrT> index, Label* if_end);

        // Specialization for Smi.
        // The {result} variable will contain the entry index if the key was found,
        // or the hash code otherwise.
        template <typename CollectionType>
        void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged,
            Variable* result, Label* entry_found,
            Label* not_found);
        void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same,
            Label* if_not_same);

        // Specialization for heap numbers.
        // The {result} variable will contain the entry index if the key was found,
        // or the hash code otherwise.
        void SameValueZeroHeapNumber(Node* key_string, Node* candidate_key,
            Label* if_same, Label* if_not_same);
        template <typename CollectionType>
        void FindOrderedHashTableEntryForHeapNumberKey(Node* context, Node* table,
            Node* key_heap_number,
            Variable* result,
            Label* entry_found,
            Label* not_found);

        // Specialization for bigints.
        // The {result} variable will contain the entry index if the key was found,
        // or the hash code otherwise.
        void SameValueZeroBigInt(Node* key, Node* candidate_key, Label* if_same,
            Label* if_not_same);
        template <typename CollectionType>
        void FindOrderedHashTableEntryForBigIntKey(Node* context, Node* table,
            Node* key, Variable* result,
            Label* entry_found,
            Label* not_found);

        // Specialization for string.
        // The {result} variable will contain the entry index if the key was found,
        // or the hash code otherwise.
        template <typename CollectionType>
        void FindOrderedHashTableEntryForStringKey(Node* context, Node* table,
            Node* key_tagged, Variable* result,
            Label* entry_found,
            Label* not_found);
        Node* ComputeStringHash(Node* context, Node* string_key);
        void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key,
            Label* if_same, Label* if_not_same);

        // Specialization for non-strings, non-numbers. For those we only need
        // reference equality to compare the keys.
        // The {result} variable will contain the entry index if the key was found,
        // or the hash code otherwise. If the hash-code has not been computed, it
        // should be Smi -1.
        template <typename CollectionType>
        void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table,
            Node* key, Variable* result,
            Label* entry_found,
            Label* not_found);

        template <typename CollectionType>
        void TryLookupOrderedHashTableIndex(Node* const table, Node* const key,
            Node* const context, Variable* result,
            Label* if_entry_found,
            Label* if_not_found);

        Node* NormalizeNumberKey(Node* key);
        void StoreOrderedHashMapNewEntry(TNode<OrderedHashMap> const table,
            Node* const key, Node* const value,
            Node* const hash,
            Node* const number_of_buckets,
            Node* const occupancy);
        void StoreOrderedHashSetNewEntry(TNode<OrderedHashSet> const table,
            Node* const key, Node* const hash,
            Node* const number_of_buckets,
            Node* const occupancy);

        // Create a JSArray with PACKED_ELEMENTS kind from a Map.prototype.keys() or
        // Map.prototype.values() iterator. The iterator is assumed to satisfy
        // IterableWithOriginalKeyOrValueMapIterator. This function will skip the
        // iterator and iterate directly on the underlying hash table. In the end it
        // will update the state of the iterator to 'exhausted'.
        TNode<JSArray> MapIteratorToList(TNode<Context> context,
            TNode<JSMapIterator> iterator);

        // Create a JSArray with PACKED_ELEMENTS kind from a Set.prototype.keys() or
        // Set.prototype.values() iterator, or a Set. The |iterable| is assumed to
        // satisfy IterableWithOriginalValueSetIterator. This function will skip the
        // iterator and iterate directly on the underlying hash table. In the end, if
        // |iterable| is an iterator, it will update the state of the iterator to
        // 'exhausted'.
        TNode<JSArray> SetOrSetIteratorToList(TNode<Context> context,
            TNode<Object> iterable);

        void BranchIfMapIteratorProtectorValid(Label* if_true, Label* if_false);
        void BranchIfSetIteratorProtectorValid(Label* if_true, Label* if_false);
    };

    template <typename IteratorType>
    Node* CollectionsBuiltinsAssembler::AllocateJSCollectionIterator(
        Node* context, int map_index, Node* collection)
    {
        Node* const table = LoadObjectField(collection, JSCollection::kTableOffset);
        Node* const native_context = LoadNativeContext(context);
        Node* const iterator_map = LoadContextElement(native_context, map_index);
        Node* const iterator = AllocateInNewSpace(IteratorType::kSize);
        StoreMapNoWriteBarrier(iterator, iterator_map);
        StoreObjectFieldRoot(iterator, IteratorType::kPropertiesOrHashOffset,
            RootIndex::kEmptyFixedArray);
        StoreObjectFieldRoot(iterator, IteratorType::kElementsOffset,
            RootIndex::kEmptyFixedArray);
        StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kTableOffset, table);
        StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
            SmiConstant(0));
        return iterator;
    }

    TNode<Object> CollectionsBuiltinsAssembler::AllocateTable(
        Variant variant, TNode<Context> context,
        TNode<IntPtrT> at_least_space_for)
    {
        return CAST((variant == kMap || variant == kWeakMap)
                ? AllocateOrderedHashTable<OrderedHashMap>()
                : AllocateOrderedHashTable<OrderedHashSet>());
    }

    TF_BUILTIN(MapConstructor, CollectionsBuiltinsAssembler)
    {
        TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
        TNode<IntPtrT> argc = ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));

        GenerateConstructor(kMap, isolate()->factory()->Map_string(), new_target,
            argc, context);
    }

    TF_BUILTIN(SetConstructor, CollectionsBuiltinsAssembler)
    {
        TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
        TNode<IntPtrT> argc = ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));

        GenerateConstructor(kSet, isolate()->factory()->Set_string(), new_target,
            argc, context);
    }

    Node* CollectionsBuiltinsAssembler::CallGetOrCreateHashRaw(Node* const key)
    {
        Node* const function_addr = ExternalConstant(ExternalReference::get_or_create_hash_raw());
        Node* const isolate_ptr = ExternalConstant(ExternalReference::isolate_address(isolate()));

        MachineType type_ptr = MachineType::Pointer();
        MachineType type_tagged = MachineType::AnyTagged();

        Node* const result = CallCFunction(function_addr, type_tagged,
            std::make_pair(type_ptr, isolate_ptr),
            std::make_pair(type_tagged, key));

        return result;
    }

    Node* CollectionsBuiltinsAssembler::CallGetHashRaw(Node* const key)
    {
        Node* const function_addr = ExternalConstant(ExternalReference::orderedhashmap_gethash_raw());
        Node* const isolate_ptr = ExternalConstant(ExternalReference::isolate_address(isolate()));

        MachineType type_ptr = MachineType::Pointer();
        MachineType type_tagged = MachineType::AnyTagged();

        Node* const result = CallCFunction(function_addr, type_tagged,
            std::make_pair(type_ptr, isolate_ptr),
            std::make_pair(type_tagged, key));

        return SmiUntag(result);
    }

    Node* CollectionsBuiltinsAssembler::GetHash(Node* const key)
    {
        VARIABLE(var_hash, MachineType::PointerRepresentation());
        Label if_receiver(this), if_other(this), done(this);
        Branch(IsJSReceiver(key), &if_receiver, &if_other);

        BIND(&if_receiver);
        {
            var_hash.Bind(LoadJSReceiverIdentityHash(key));
            Goto(&done);
        }

        BIND(&if_other);
        {
            var_hash.Bind(CallGetHashRaw(key));
            Goto(&done);
        }

        BIND(&done);
        return var_hash.value();
    }

    void CollectionsBuiltinsAssembler::SameValueZeroSmi(Node* key_smi,
        Node* candidate_key,
        Label* if_same,
        Label* if_not_same)
    {
        // If the key is the same, we are done.
        GotoIf(WordEqual(candidate_key, key_smi), if_same);

        // If the candidate key is smi, then it must be different (because
        // we already checked for equality above).
        GotoIf(TaggedIsSmi(candidate_key), if_not_same);

        // If the candidate key is not smi, we still have to check if it is a
        // heap number with the same value.
        GotoIfNot(IsHeapNumber(candidate_key), if_not_same);

        Node* const candidate_key_number = LoadHeapNumberValue(candidate_key);
        Node* const key_number = SmiToFloat64(key_smi);

        GotoIf(Float64Equal(candidate_key_number, key_number), if_same);

        Goto(if_not_same);
    }

    void CollectionsBuiltinsAssembler::BranchIfMapIteratorProtectorValid(
        Label* if_true, Label* if_false)
    {
        Node* protector_cell = LoadRoot(RootIndex::kMapIteratorProtector);
        DCHECK(isolate()->heap()->map_iterator_protector()->IsPropertyCell());
        Branch(WordEqual(LoadObjectField(protector_cell, PropertyCell::kValueOffset),
                   SmiConstant(Isolate::kProtectorValid)),
            if_true, if_false);
    }

    void CollectionsBuiltinsAssembler::
        BranchIfIterableWithOriginalKeyOrValueMapIterator(TNode<Object> iterator,
            TNode<Context> context,
            Label* if_true,
            Label* if_false)
    {
        Label if_key_or_value_iterator(this), extra_checks(this);

        // Check if iterator is a keys or values JSMapIterator.
        GotoIf(TaggedIsSmi(iterator), if_false);
        TNode<Map> iter_map = LoadMap(CAST(iterator));
        Node* const instance_type = LoadMapInstanceType(iter_map);
        GotoIf(InstanceTypeEqual(instance_type, JS_MAP_KEY_ITERATOR_TYPE),
            &if_key_or_value_iterator);
        Branch(InstanceTypeEqual(instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
            &if_key_or_value_iterator, if_false);

        BIND(&if_key_or_value_iterator);
        // Check that the iterator is not partially consumed.
        Node* const index = LoadObjectField(CAST(iterator), JSMapIterator::kIndexOffset);
        GotoIfNot(WordEqual(index, SmiConstant(0)), if_false);
        BranchIfMapIteratorProtectorValid(&extra_checks, if_false);

        BIND(&extra_checks);
        // Check if the iterator object has the original %MapIteratorPrototype%.
        Node* const native_context = LoadNativeContext(context);
        Node* const initial_map_iter_proto = LoadContextElement(
            native_context, Context::INITIAL_MAP_ITERATOR_PROTOTYPE_INDEX);
        Node* const map_iter_proto = LoadMapPrototype(iter_map);
        GotoIfNot(WordEqual(map_iter_proto, initial_map_iter_proto), if_false);

        // Check if the original MapIterator prototype has the original
        // %IteratorPrototype%.
        Node* const initial_iter_proto = LoadContextElement(
            native_context, Context::INITIAL_ITERATOR_PROTOTYPE_INDEX);
        Node* const iter_proto = LoadMapPrototype(LoadMap(map_iter_proto));
        Branch(WordEqual(iter_proto, initial_iter_proto), if_true, if_false);
    }

    void BranchIfIterableWithOriginalKeyOrValueMapIterator(
        compiler::CodeAssemblerState* state, TNode<Object> iterable,
        TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
        compiler::CodeAssemblerLabel* if_false)
    {
        CollectionsBuiltinsAssembler assembler(state);
        assembler.BranchIfIterableWithOriginalKeyOrValueMapIterator(
            iterable, context, if_true, if_false);
    }

    void CollectionsBuiltinsAssembler::BranchIfSetIteratorProtectorValid(
        Label* if_true, Label* if_false)
    {
        Node* const protector_cell = LoadRoot(RootIndex::kSetIteratorProtector);
        DCHECK(isolate()->heap()->set_iterator_protector()->IsPropertyCell());
        Branch(WordEqual(LoadObjectField(protector_cell, PropertyCell::kValueOffset),
                   SmiConstant(Isolate::kProtectorValid)),
            if_true, if_false);
    }

    void CollectionsBuiltinsAssembler::BranchIfIterableWithOriginalValueSetIterator(
        TNode<Object> iterable, TNode<Context> context, Label* if_true,
        Label* if_false)
    {
        Label if_set(this), if_value_iterator(this), check_protector(this);
        TVARIABLE(BoolT, var_result);

        GotoIf(TaggedIsSmi(iterable), if_false);
        TNode<Map> iterable_map = LoadMap(CAST(iterable));
        Node* const instance_type = LoadMapInstanceType(iterable_map);

        GotoIf(InstanceTypeEqual(instance_type, JS_SET_TYPE), &if_set);
        Branch(InstanceTypeEqual(instance_type, JS_SET_VALUE_ITERATOR_TYPE),
            &if_value_iterator, if_false);

        BIND(&if_set);
        // Check if the set object has the original Set prototype.
        Node* const initial_set_proto = LoadContextElement(
            LoadNativeContext(context), Context::INITIAL_SET_PROTOTYPE_INDEX);
        Node* const set_proto = LoadMapPrototype(iterable_map);
        GotoIfNot(WordEqual(set_proto, initial_set_proto), if_false);
        Goto(&check_protector);

        BIND(&if_value_iterator);
        // Check that the iterator is not partially consumed.
        Node* const index = LoadObjectField(CAST(iterable), JSSetIterator::kIndexOffset);
        GotoIfNot(WordEqual(index, SmiConstant(0)), if_false);

        // Check if the iterator object has the original SetIterator prototype.
        Node* const native_context = LoadNativeContext(context);
        Node* const initial_set_iter_proto = LoadContextElement(
            native_context, Context::INITIAL_SET_ITERATOR_PROTOTYPE_INDEX);
        Node* const set_iter_proto = LoadMapPrototype(iterable_map);
        GotoIfNot(WordEqual(set_iter_proto, initial_set_iter_proto), if_false);

        // Check if the original SetIterator prototype has the original
        // %IteratorPrototype%.
        Node* const initial_iter_proto = LoadContextElement(
            native_context, Context::INITIAL_ITERATOR_PROTOTYPE_INDEX);
        Node* const iter_proto = LoadMapPrototype(LoadMap(set_iter_proto));
        GotoIfNot(WordEqual(iter_proto, initial_iter_proto), if_false);
        Goto(&check_protector);

        BIND(&check_protector);
        BranchIfSetIteratorProtectorValid(if_true, if_false);
    }

    void BranchIfIterableWithOriginalValueSetIterator(
        compiler::CodeAssemblerState* state, TNode<Object> iterable,
        TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
        compiler::CodeAssemblerLabel* if_false)
    {
        CollectionsBuiltinsAssembler assembler(state);
        assembler.BranchIfIterableWithOriginalValueSetIterator(iterable, context,
            if_true, if_false);
    }

    TNode<JSArray> CollectionsBuiltinsAssembler::MapIteratorToList(
        TNode<Context> context, TNode<JSMapIterator> iterator)
    {
        // Transition the {iterator} table if necessary.
        TNode<OrderedHashMap> table;
        TNode<IntPtrT> index;
        std::tie(table, index) = TransitionAndUpdate<JSMapIterator, OrderedHashMap>(iterator);
        CSA_ASSERT(this, IntPtrEqual(index, IntPtrConstant(0)));

        TNode<IntPtrT> size = LoadAndUntagObjectField(table, OrderedHashMap::NumberOfElementsOffset());

        const ElementsKind kind = PACKED_ELEMENTS;
        TNode<Map> array_map = LoadJSArrayElementsMap(kind, LoadNativeContext(context));
        TNode<JSArray> array = AllocateJSArray(kind, array_map, size, SmiTag(size), nullptr,
            INTPTR_PARAMETERS, kAllowLargeObjectAllocation);
        TNode<FixedArray> elements = CAST(LoadElements(array));

        const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
        TNode<IntPtrT> first_to_element_offset = ElementOffsetFromIndex(IntPtrConstant(0), kind, INTPTR_PARAMETERS, 0);
        VARIABLE(
            var_offset, MachineType::PointerRepresentation(),
            IntPtrAdd(first_to_element_offset, IntPtrConstant(first_element_offset)));
        TVARIABLE(IntPtrT, var_index, index);
        VariableList vars({ &var_index, &var_offset }, zone());
        Label done(this, { &var_index }), loop(this, vars), continue_loop(this, vars),
            write_key(this, vars), write_value(this, vars);

        Goto(&loop);

        BIND(&loop);
        {
            // Read the next entry from the {table}, skipping holes.
            TNode<Object> entry_key;
            TNode<IntPtrT> entry_start_position;
            TNode<IntPtrT> cur_index;
            std::tie(entry_key, entry_start_position, cur_index) = NextSkipHoles<OrderedHashMap>(table, var_index.value(), &done);

            // Decide to write key or value.
            Branch(
                InstanceTypeEqual(LoadInstanceType(iterator), JS_MAP_KEY_ITERATOR_TYPE),
                &write_key, &write_value);

            BIND(&write_key);
            {
                Store(elements, var_offset.value(), entry_key);
                Goto(&continue_loop);
            }

            BIND(&write_value);
            {
                CSA_ASSERT(this, InstanceTypeEqual(LoadInstanceType(iterator), JS_MAP_VALUE_ITERATOR_TYPE));
                TNode<Object> entry_value = UnsafeLoadFixedArrayElement(table, entry_start_position,
                    (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) * kTaggedSize);

                Store(elements, var_offset.value(), entry_value);
                Goto(&continue_loop);
            }

            BIND(&continue_loop);
            {
                // Increment the array offset and continue the loop to the next entry.
                var_index = cur_index;
                var_offset.Bind(
                    IntPtrAdd(var_offset.value(), IntPtrConstant(kTaggedSize)));
                Goto(&loop);
            }
        }

        BIND(&done);
        // Set the {iterator} to exhausted.
        StoreObjectFieldRoot(iterator, JSMapIterator::kTableOffset,
            RootIndex::kEmptyOrderedHashMap);
        StoreObjectFieldNoWriteBarrier(iterator, JSMapIterator::kIndexOffset,
            SmiTag(var_index.value()));
        return UncheckedCast<JSArray>(array);
    }

    TF_BUILTIN(MapIteratorToList, CollectionsBuiltinsAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<JSMapIterator> iterator = CAST(Parameter(Descriptor::kSource));
        Return(MapIteratorToList(context, iterator));
    }

    TNode<JSArray> CollectionsBuiltinsAssembler::SetOrSetIteratorToList(
        TNode<Context> context, TNode<Object> iterable)
    {
        TVARIABLE(OrderedHashSet, var_table);
        Label if_set(this), if_iterator(this), copy(this);

        Node* const instance_type = LoadInstanceType(CAST(iterable));
        Branch(InstanceTypeEqual(instance_type, JS_SET_TYPE), &if_set, &if_iterator);

        BIND(&if_set);
        {
            // {iterable} is a JSSet.
            var_table = CAST(LoadObjectField(CAST(iterable), JSSet::kTableOffset));
            Goto(&copy);
        }

        BIND(&if_iterator);
        {
            // {iterable} is a JSSetIterator.
            // Transition the {iterable} table if necessary.
            TNode<OrderedHashSet> iter_table;
            TNode<IntPtrT> iter_index;
            std::tie(iter_table, iter_index) = TransitionAndUpdate<JSSetIterator, OrderedHashSet>(CAST(iterable));
            CSA_ASSERT(this, IntPtrEqual(iter_index, IntPtrConstant(0)));
            var_table = iter_table;
            Goto(&copy);
        }

        BIND(&copy);
        TNode<OrderedHashSet> table = var_table.value();
        TNode<IntPtrT> size = LoadAndUntagObjectField(table, OrderedHashMap::NumberOfElementsOffset());

        const ElementsKind kind = PACKED_ELEMENTS;
        TNode<Map> array_map = LoadJSArrayElementsMap(kind, LoadNativeContext(context));
        TNode<JSArray> array = AllocateJSArray(kind, array_map, size, SmiTag(size), nullptr,
            INTPTR_PARAMETERS, kAllowLargeObjectAllocation);
        TNode<FixedArray> elements = CAST(LoadElements(array));

        const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
        TNode<IntPtrT> first_to_element_offset = ElementOffsetFromIndex(IntPtrConstant(0), kind, INTPTR_PARAMETERS, 0);
        VARIABLE(
            var_offset, MachineType::PointerRepresentation(),
            IntPtrAdd(first_to_element_offset, IntPtrConstant(first_element_offset)));
        TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
        Label done(this), finalize(this, { &var_index }),
            loop(this, { &var_index, &var_offset });

        Goto(&loop);

        BIND(&loop);
        {
            // Read the next entry from the {table}, skipping holes.
            TNode<Object> entry_key;
            TNode<IntPtrT> entry_start_position;
            TNode<IntPtrT> cur_index;
            std::tie(entry_key, entry_start_position, cur_index) = NextSkipHoles<OrderedHashSet>(table, var_index.value(), &finalize);

            Store(elements, var_offset.value(), entry_key);

            var_index = cur_index;
            var_offset.Bind(IntPtrAdd(var_offset.value(), IntPtrConstant(kTaggedSize)));
            Goto(&loop);
        }

        BIND(&finalize);
        GotoIf(InstanceTypeEqual(instance_type, JS_SET_TYPE), &done);
        // Set the {iterable} to exhausted if it's an iterator.
        StoreObjectFieldRoot(iterable, JSSetIterator::kTableOffset,
            RootIndex::kEmptyOrderedHashSet);
        StoreObjectFieldNoWriteBarrier(iterable, JSSetIterator::kIndexOffset,
            SmiTag(var_index.value()));
        Goto(&done);

        BIND(&done);
        return UncheckedCast<JSArray>(array);
    }

    TF_BUILTIN(SetOrSetIteratorToList, CollectionsBuiltinsAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<Object> object = CAST(Parameter(Descriptor::kSource));
        Return(SetOrSetIteratorToList(context, object));
    }

    template <typename CollectionType>
    void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey(
        Node* table, Node* smi_key, Variable* result, Label* entry_found,
        Label* not_found)
    {
        Node* const key_untagged = SmiUntag(smi_key);
        Node* const hash = ChangeInt32ToIntPtr(ComputeUnseededHash(key_untagged));
        CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
        result->Bind(hash);
        FindOrderedHashTableEntry<CollectionType>(
            table, hash,
            [&](Node* other_key, Label* if_same, Label* if_not_same) {
                SameValueZeroSmi(smi_key, other_key, if_same, if_not_same);
            },
            result, entry_found, not_found);
    }

    template <typename CollectionType>
    void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey(
        Node* context, Node* table, Node* key_tagged, Variable* result,
        Label* entry_found, Label* not_found)
    {
        Node* const hash = ComputeStringHash(context, key_tagged);
        CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
        result->Bind(hash);
        FindOrderedHashTableEntry<CollectionType>(
            table, hash,
            [&](Node* other_key, Label* if_same, Label* if_not_same) {
                SameValueZeroString(context, key_tagged, other_key, if_same,
                    if_not_same);
            },
            result, entry_found, not_found);
    }

    template <typename CollectionType>
    void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey(
        Node* context, Node* table, Node* key_heap_number, Variable* result,
        Label* entry_found, Label* not_found)
    {
        Node* hash = CallGetHashRaw(key_heap_number);
        CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
        result->Bind(hash);
        Node* const key_float = LoadHeapNumberValue(key_heap_number);
        FindOrderedHashTableEntry<CollectionType>(
            table, hash,
            [&](Node* other_key, Label* if_same, Label* if_not_same) {
                SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same);
            },
            result, entry_found, not_found);
    }

    template <typename CollectionType>
    void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForBigIntKey(
        Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
        Label* not_found)
    {
        Node* hash = CallGetHashRaw(key);
        CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
        result->Bind(hash);
        FindOrderedHashTableEntry<CollectionType>(
            table, hash,
            [&](Node* other_key, Label* if_same, Label* if_not_same) {
                SameValueZeroBigInt(key, other_key, if_same, if_not_same);
            },
            result, entry_found, not_found);
    }

    template <typename CollectionType>
    void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey(
        Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
        Label* not_found)
    {
        Node* hash = GetHash(key);
        CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
        result->Bind(hash);
        FindOrderedHashTableEntry<CollectionType>(
            table, hash,
            [&](Node* other_key, Label* if_same, Label* if_not_same) {
                Branch(WordEqual(key, other_key), if_same, if_not_same);
            },
            result, entry_found, not_found);
    }

    Node* CollectionsBuiltinsAssembler::ComputeStringHash(Node* context,
        Node* string_key)
    {
        VARIABLE(var_result, MachineType::PointerRepresentation());

        Label hash_not_computed(this), done(this, &var_result);
        Node* hash = ChangeInt32ToIntPtr(LoadNameHash(string_key, &hash_not_computed));
        var_result.Bind(hash);
        Goto(&done);

        BIND(&hash_not_computed);
        var_result.Bind(CallGetHashRaw(string_key));
        Goto(&done);

        BIND(&done);
        return var_result.value();
    }

    void CollectionsBuiltinsAssembler::SameValueZeroString(Node* context,
        Node* key_string,
        Node* candidate_key,
        Label* if_same,
        Label* if_not_same)
    {
        // If the candidate is not a string, the keys are not equal.
        GotoIf(TaggedIsSmi(candidate_key), if_not_same);
        GotoIfNot(IsString(candidate_key), if_not_same);

        Branch(WordEqual(CallBuiltin(Builtins::kStringEqual, context, key_string,
                             candidate_key),
                   TrueConstant()),
            if_same, if_not_same);
    }

    void CollectionsBuiltinsAssembler::SameValueZeroBigInt(Node* key,
        Node* candidate_key,
        Label* if_same,
        Label* if_not_same)
    {
        CSA_ASSERT(this, IsBigInt(key));
        GotoIf(TaggedIsSmi(candidate_key), if_not_same);
        GotoIfNot(IsBigInt(candidate_key), if_not_same);

        Branch(WordEqual(CallRuntime(Runtime::kBigIntEqualToBigInt,
                             NoContextConstant(), key, candidate_key),
                   TrueConstant()),
            if_same, if_not_same);
    }

    void CollectionsBuiltinsAssembler::SameValueZeroHeapNumber(Node* key_float,
        Node* candidate_key,
        Label* if_same,
        Label* if_not_same)
    {
        Label if_smi(this), if_keyisnan(this);

        GotoIf(TaggedIsSmi(candidate_key), &if_smi);
        GotoIfNot(IsHeapNumber(candidate_key), if_not_same);

        {
            // {candidate_key} is a heap number.
            Node* const candidate_float = LoadHeapNumberValue(candidate_key);
            GotoIf(Float64Equal(key_float, candidate_float), if_same);

            // SameValueZero needs to treat NaNs as equal. First check if {key_float}
            // is NaN.
            BranchIfFloat64IsNaN(key_float, &if_keyisnan, if_not_same);

            BIND(&if_keyisnan);
            {
                // Return true iff {candidate_key} is NaN.
                Branch(Float64Equal(candidate_float, candidate_float), if_not_same,
                    if_same);
            }
        }

        BIND(&if_smi);
        {
            Node* const candidate_float = SmiToFloat64(candidate_key);
            Branch(Float64Equal(key_float, candidate_float), if_same, if_not_same);
        }
    }

    TF_BUILTIN(OrderedHashTableHealIndex, CollectionsBuiltinsAssembler)
    {
        TNode<HeapObject> table = CAST(Parameter(Descriptor::kTable));
        TNode<Smi> index = CAST(Parameter(Descriptor::kIndex));
        Label return_index(this), return_zero(this);

        // Check if we need to update the {index}.
        GotoIfNot(SmiLessThan(SmiConstant(0), index), &return_zero);

        // Check if the {table} was cleared.
        STATIC_ASSERT(OrderedHashMap::NumberOfDeletedElementsOffset() == OrderedHashSet::NumberOfDeletedElementsOffset());
        Node* number_of_deleted_elements = LoadAndUntagObjectField(
            table, OrderedHashMap::NumberOfDeletedElementsOffset());
        STATIC_ASSERT(OrderedHashMap::kClearedTableSentinel == OrderedHashSet::kClearedTableSentinel);
        GotoIf(WordEqual(number_of_deleted_elements,
                   IntPtrConstant(OrderedHashMap::kClearedTableSentinel)),
            &return_zero);

        VARIABLE(var_i, MachineType::PointerRepresentation(), IntPtrConstant(0));
        VARIABLE(var_index, MachineRepresentation::kTagged, index);
        Label loop(this, { &var_i, &var_index });
        Goto(&loop);
        BIND(&loop);
        {
            Node* i = var_i.value();
            GotoIfNot(IntPtrLessThan(i, number_of_deleted_elements), &return_index);
            STATIC_ASSERT(OrderedHashMap::RemovedHolesIndex() == OrderedHashSet::RemovedHolesIndex());
            TNode<Smi> removed_index = CAST(LoadFixedArrayElement(
                CAST(table), i, OrderedHashMap::RemovedHolesIndex() * kTaggedSize));
            GotoIf(SmiGreaterThanOrEqual(removed_index, index), &return_index);
            Decrement(&var_index, 1, SMI_PARAMETERS);
            Increment(&var_i);
            Goto(&loop);
        }

        BIND(&return_index);
        Return(var_index.value());

        BIND(&return_zero);
        Return(SmiConstant(0));
    }

    template <typename TableType>
    std::pair<TNode<TableType>, TNode<IntPtrT>>
    CollectionsBuiltinsAssembler::Transition(
        TNode<TableType> const table, TNode<IntPtrT> const index,
        UpdateInTransition const& update_in_transition)
    {
        TVARIABLE(IntPtrT, var_index, index);
        TVARIABLE(TableType, var_table, table);
        Label if_done(this), if_transition(this, Label::kDeferred);
        Branch(TaggedIsSmi(
                   LoadObjectField(var_table.value(), TableType::NextTableOffset())),
            &if_done, &if_transition);

        BIND(&if_transition);
        {
            Label loop(this, { &var_table, &var_index }), done_loop(this);
            Goto(&loop);
            BIND(&loop);
            {
                TNode<TableType> table = var_table.value();
                TNode<IntPtrT> index = var_index.value();

                TNode<Object> next_table = LoadObjectField(table, TableType::NextTableOffset());
                GotoIf(TaggedIsSmi(next_table), &done_loop);

                var_table = CAST(next_table);
                var_index = SmiUntag(
                    CAST(CallBuiltin(Builtins::kOrderedHashTableHealIndex,
                        NoContextConstant(), table, SmiTag(index))));
                Goto(&loop);
            }
            BIND(&done_loop);

            // Update with the new {table} and {index}.
            update_in_transition(var_table.value(), var_index.value());
            Goto(&if_done);
        }

        BIND(&if_done);
        return { var_table.value(), var_index.value() };
    }

    template <typename IteratorType, typename TableType>
    std::pair<TNode<TableType>, TNode<IntPtrT>>
    CollectionsBuiltinsAssembler::TransitionAndUpdate(
        TNode<IteratorType> const iterator)
    {
        return Transition<TableType>(
            CAST(LoadObjectField(iterator, IteratorType::kTableOffset)),
            LoadAndUntagObjectField(iterator, IteratorType::kIndexOffset),
            [this, iterator](Node* const table, Node* const index) {
                // Update the {iterator} with the new state.
                StoreObjectField(iterator, IteratorType::kTableOffset, table);
                StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
                    SmiTag(index));
            });
    }

    template <typename TableType>
    std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>>
    CollectionsBuiltinsAssembler::NextSkipHoles(TNode<TableType> table,
        TNode<IntPtrT> index,
        Label* if_end)
    {
        // Compute the used capacity for the {table}.
        TNode<IntPtrT> number_of_buckets = LoadAndUntagObjectField(table, TableType::NumberOfBucketsOffset());
        TNode<IntPtrT> number_of_elements = LoadAndUntagObjectField(table, TableType::NumberOfElementsOffset());
        TNode<IntPtrT> number_of_deleted_elements = LoadAndUntagObjectField(
            table, TableType::NumberOfDeletedElementsOffset());
        TNode<IntPtrT> used_capacity = IntPtrAdd(number_of_elements, number_of_deleted_elements);

        TNode<Object> entry_key;
        TNode<IntPtrT> entry_start_position;
        TVARIABLE(IntPtrT, var_index, index);
        Label loop(this, &var_index), done_loop(this);
        Goto(&loop);
        BIND(&loop);
        {
            GotoIfNot(IntPtrLessThan(var_index.value(), used_capacity), if_end);
            entry_start_position = IntPtrAdd(
                IntPtrMul(var_index.value(), IntPtrConstant(TableType::kEntrySize)),
                number_of_buckets);
            entry_key = UnsafeLoadFixedArrayElement(
                table, entry_start_position,
                TableType::HashTableStartIndex() * kTaggedSize);
            Increment(&var_index);
            Branch(IsTheHole(entry_key), &loop, &done_loop);
        }

        BIND(&done_loop);
        return std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>> {
            entry_key, entry_start_position, var_index.value()
        };
    }

    TF_BUILTIN(MapPrototypeGet, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get");

        Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
        TNode<Smi> index = CAST(
            CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key));

        Label if_found(this), if_not_found(this);
        Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
            &if_not_found);

        BIND(&if_found);
        Return(LoadFixedArrayElement(
            CAST(table), SmiUntag(index),
            (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) * kTaggedSize));

        BIND(&if_not_found);
        Return(UndefinedConstant());
    }

    TF_BUILTIN(MapPrototypeHas, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has");

        Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
        TNode<Smi> index = CAST(
            CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key));

        Label if_found(this), if_not_found(this);
        Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
            &if_not_found);

        BIND(&if_found);
        Return(TrueConstant());

        BIND(&if_not_found);
        Return(FalseConstant());
    }

    Node* CollectionsBuiltinsAssembler::NormalizeNumberKey(Node* const key)
    {
        VARIABLE(result, MachineRepresentation::kTagged, key);
        Label done(this);

        GotoIf(TaggedIsSmi(key), &done);
        GotoIfNot(IsHeapNumber(key), &done);
        Node* const number = LoadHeapNumberValue(key);
        GotoIfNot(Float64Equal(number, Float64Constant(0.0)), &done);
        // We know the value is zero, so we take the key to be Smi 0.
        // Another option would be to normalize to Smi here.
        result.Bind(SmiConstant(0));
        Goto(&done);

        BIND(&done);
        return result.value();
    }

    TF_BUILTIN(MapPrototypeSet, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* key = Parameter(Descriptor::kKey);
        Node* const value = Parameter(Descriptor::kValue);
        Node* const context = Parameter(Descriptor::kContext);

        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.set");

        key = NormalizeNumberKey(key);

        TNode<OrderedHashMap> const table = CAST(LoadObjectField(receiver, JSMap::kTableOffset));

        VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
            IntPtrConstant(0));
        Label entry_found(this), not_found(this);

        TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
            &entry_start_position_or_hash,
            &entry_found, &not_found);

        BIND(&entry_found);
        // If we found the entry, we just store the value there.
        StoreFixedArrayElement(table, entry_start_position_or_hash.value(), value,
            UPDATE_WRITE_BARRIER,
            kTaggedSize * (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset));
        Return(receiver);

        Label no_hash(this), add_entry(this), store_new_entry(this);
        BIND(&not_found);
        {
            // If we have a hash code, we can start adding the new entry.
            GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
                       IntPtrConstant(0)),
                &add_entry);

            // Otherwise, go to runtime to compute the hash code.
            entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
            Goto(&add_entry);
        }

        BIND(&add_entry);
        VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
        VARIABLE(occupancy, MachineType::PointerRepresentation());
        TVARIABLE(OrderedHashMap, table_var, table);
        {
            // Check we have enough space for the entry.
            number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
                table, OrderedHashMap::NumberOfBucketsIndex()))));

            STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2);
            Node* const capacity = WordShl(number_of_buckets.value(), 1);
            Node* const number_of_elements = SmiUntag(
                CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())));
            Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
                table, OrderedHashMap::NumberOfDeletedElementsOffset())));
            occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
            GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);

            // We do not have enough space, grow the table and reload the relevant
            // fields.
            CallRuntime(Runtime::kMapGrow, context, receiver);
            table_var = CAST(LoadObjectField(receiver, JSMap::kTableOffset));
            number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
                table_var.value(), OrderedHashMap::NumberOfBucketsIndex()))));
            Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
                table_var.value(), OrderedHashMap::NumberOfElementsOffset())));
            Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
                table_var.value(), OrderedHashMap::NumberOfDeletedElementsOffset())));
            occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
            Goto(&store_new_entry);
        }
        BIND(&store_new_entry);
        // Store the key, value and connect the element to the bucket chain.
        StoreOrderedHashMapNewEntry(table_var.value(), key, value,
            entry_start_position_or_hash.value(),
            number_of_buckets.value(), occupancy.value());
        Return(receiver);
    }

    void CollectionsBuiltinsAssembler::StoreOrderedHashMapNewEntry(
        TNode<OrderedHashMap> const table, Node* const key, Node* const value,
        Node* const hash, Node* const number_of_buckets, Node* const occupancy)
    {
        Node* const bucket = WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
        Node* const bucket_entry = UnsafeLoadFixedArrayElement(
            table, bucket, OrderedHashMap::HashTableStartIndex() * kTaggedSize);

        // Store the entry elements.
        Node* const entry_start = IntPtrAdd(
            IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)),
            number_of_buckets);
        UnsafeStoreFixedArrayElement(
            table, entry_start, key, UPDATE_WRITE_BARRIER,
            kTaggedSize * OrderedHashMap::HashTableStartIndex());
        UnsafeStoreFixedArrayElement(
            table, entry_start, value, UPDATE_WRITE_BARRIER,
            kTaggedSize * (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset));
        UnsafeStoreFixedArrayElement(
            table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
            kTaggedSize * (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kChainOffset));

        // Update the bucket head.
        UnsafeStoreFixedArrayElement(
            table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
            OrderedHashMap::HashTableStartIndex() * kTaggedSize);

        // Bump the elements count.
        TNode<Smi> const number_of_elements = CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset()));
        StoreObjectFieldNoWriteBarrier(table,
            OrderedHashMap::NumberOfElementsOffset(),
            SmiAdd(number_of_elements, SmiConstant(1)));
    }

    TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
            "Map.prototype.delete");

        TNode<OrderedHashMap> const table = CAST(LoadObjectField(receiver, JSMap::kTableOffset));

        VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
            IntPtrConstant(0));
        Label entry_found(this), not_found(this);

        TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
            &entry_start_position_or_hash,
            &entry_found, &not_found);

        BIND(&not_found);
        Return(FalseConstant());

        BIND(&entry_found);
        // If we found the entry, mark the entry as deleted.
        StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
            TheHoleConstant(), UPDATE_WRITE_BARRIER,
            kTaggedSize * OrderedHashMap::HashTableStartIndex());
        StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
            TheHoleConstant(), UPDATE_WRITE_BARRIER,
            kTaggedSize * (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset));

        // Decrement the number of elements, increment the number of deleted elements.
        TNode<Smi> const number_of_elements = SmiSub(
            CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())),
            SmiConstant(1));
        StoreObjectFieldNoWriteBarrier(
            table, OrderedHashMap::NumberOfElementsOffset(), number_of_elements);
        TNode<Smi> const number_of_deleted = SmiAdd(CAST(LoadObjectField(
                                                        table, OrderedHashMap::NumberOfDeletedElementsOffset())),
            SmiConstant(1));
        StoreObjectFieldNoWriteBarrier(
            table, OrderedHashMap::NumberOfDeletedElementsOffset(),
            number_of_deleted);

        TNode<Smi> const number_of_buckets = CAST(
            LoadFixedArrayElement(table, OrderedHashMap::NumberOfBucketsIndex()));

        // If there fewer elements than #buckets / 2, shrink the table.
        Label shrink(this);
        GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
                   number_of_buckets),
            &shrink);
        Return(TrueConstant());

        BIND(&shrink);
        CallRuntime(Runtime::kMapShrink, context, receiver);
        Return(TrueConstant());
    }

    TF_BUILTIN(SetPrototypeAdd, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.add");

        key = NormalizeNumberKey(key);

        TNode<OrderedHashSet> const table = CAST(LoadObjectField(receiver, JSMap::kTableOffset));

        VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
            IntPtrConstant(0));
        Label entry_found(this), not_found(this);

        TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
            &entry_start_position_or_hash,
            &entry_found, &not_found);

        BIND(&entry_found);
        // The entry was found, there is nothing to do.
        Return(receiver);

        Label no_hash(this), add_entry(this), store_new_entry(this);
        BIND(&not_found);
        {
            // If we have a hash code, we can start adding the new entry.
            GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
                       IntPtrConstant(0)),
                &add_entry);

            // Otherwise, go to runtime to compute the hash code.
            entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
            Goto(&add_entry);
        }

        BIND(&add_entry);
        VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
        VARIABLE(occupancy, MachineType::PointerRepresentation());
        TVARIABLE(OrderedHashSet, table_var, table);
        {
            // Check we have enough space for the entry.
            number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
                table, OrderedHashSet::NumberOfBucketsIndex()))));

            STATIC_ASSERT(OrderedHashSet::kLoadFactor == 2);
            Node* const capacity = WordShl(number_of_buckets.value(), 1);
            Node* const number_of_elements = SmiUntag(
                CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset())));
            Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
                table, OrderedHashSet::NumberOfDeletedElementsOffset())));
            occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
            GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);

            // We do not have enough space, grow the table and reload the relevant
            // fields.
            CallRuntime(Runtime::kSetGrow, context, receiver);
            table_var = CAST(LoadObjectField(receiver, JSMap::kTableOffset));
            number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
                table_var.value(), OrderedHashSet::NumberOfBucketsIndex()))));
            Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
                table_var.value(), OrderedHashSet::NumberOfElementsOffset())));
            Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
                table_var.value(), OrderedHashSet::NumberOfDeletedElementsOffset())));
            occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
            Goto(&store_new_entry);
        }
        BIND(&store_new_entry);
        // Store the key, value and connect the element to the bucket chain.
        StoreOrderedHashSetNewEntry(table_var.value(), key,
            entry_start_position_or_hash.value(),
            number_of_buckets.value(), occupancy.value());
        Return(receiver);
    }

    void CollectionsBuiltinsAssembler::StoreOrderedHashSetNewEntry(
        TNode<OrderedHashSet> const table, Node* const key, Node* const hash,
        Node* const number_of_buckets, Node* const occupancy)
    {
        Node* const bucket = WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
        Node* const bucket_entry = UnsafeLoadFixedArrayElement(
            table, bucket, OrderedHashSet::HashTableStartIndex() * kTaggedSize);

        // Store the entry elements.
        Node* const entry_start = IntPtrAdd(
            IntPtrMul(occupancy, IntPtrConstant(OrderedHashSet::kEntrySize)),
            number_of_buckets);
        UnsafeStoreFixedArrayElement(
            table, entry_start, key, UPDATE_WRITE_BARRIER,
            kTaggedSize * OrderedHashSet::HashTableStartIndex());
        UnsafeStoreFixedArrayElement(
            table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
            kTaggedSize * (OrderedHashSet::HashTableStartIndex() + OrderedHashSet::kChainOffset));

        // Update the bucket head.
        UnsafeStoreFixedArrayElement(
            table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
            OrderedHashSet::HashTableStartIndex() * kTaggedSize);

        // Bump the elements count.
        TNode<Smi> const number_of_elements = CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset()));
        StoreObjectFieldNoWriteBarrier(table,
            OrderedHashSet::NumberOfElementsOffset(),
            SmiAdd(number_of_elements, SmiConstant(1)));
    }

    TF_BUILTIN(SetPrototypeDelete, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
            "Set.prototype.delete");

        TNode<OrderedHashSet> const table = CAST(LoadObjectField(receiver, JSMap::kTableOffset));

        VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
            IntPtrConstant(0));
        Label entry_found(this), not_found(this);

        TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
            &entry_start_position_or_hash,
            &entry_found, &not_found);

        BIND(&not_found);
        Return(FalseConstant());

        BIND(&entry_found);
        // If we found the entry, mark the entry as deleted.
        StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
            TheHoleConstant(), UPDATE_WRITE_BARRIER,
            kTaggedSize * OrderedHashSet::HashTableStartIndex());

        // Decrement the number of elements, increment the number of deleted elements.
        TNode<Smi> const number_of_elements = SmiSub(
            CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset())),
            SmiConstant(1));
        StoreObjectFieldNoWriteBarrier(
            table, OrderedHashSet::NumberOfElementsOffset(), number_of_elements);
        TNode<Smi> const number_of_deleted = SmiAdd(CAST(LoadObjectField(
                                                        table, OrderedHashSet::NumberOfDeletedElementsOffset())),
            SmiConstant(1));
        StoreObjectFieldNoWriteBarrier(
            table, OrderedHashSet::NumberOfDeletedElementsOffset(),
            number_of_deleted);

        TNode<Smi> const number_of_buckets = CAST(
            LoadFixedArrayElement(table, OrderedHashSet::NumberOfBucketsIndex()));

        // If there fewer elements than #buckets / 2, shrink the table.
        Label shrink(this);
        GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
                   number_of_buckets),
            &shrink);
        Return(TrueConstant());

        BIND(&shrink);
        CallRuntime(Runtime::kSetShrink, context, receiver);
        Return(TrueConstant());
    }

    TF_BUILTIN(MapPrototypeEntries, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);
        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
            "Map.prototype.entries");
        Return(AllocateJSCollectionIterator<JSMapIterator>(
            context, Context::MAP_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
    }

    TF_BUILTIN(MapPrototypeGetSize, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);
        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
            "get Map.prototype.size");
        Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
        Return(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset()));
    }

    TF_BUILTIN(MapPrototypeForEach, CollectionsBuiltinsAssembler)
    {
        const char* const kMethodName = "Map.prototype.forEach";
        Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
        Node* const context = Parameter(Descriptor::kContext);
        CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
        Node* const receiver = args.GetReceiver();
        Node* const callback = args.GetOptionalArgumentValue(0);
        Node* const this_arg = args.GetOptionalArgumentValue(1);

        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, kMethodName);

        // Ensure that {callback} is actually callable.
        Label callback_not_callable(this, Label::kDeferred);
        GotoIf(TaggedIsSmi(callback), &callback_not_callable);
        GotoIfNot(IsCallable(callback), &callback_not_callable);

        TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
        TVARIABLE(OrderedHashMap, var_table,
            CAST(LoadObjectField(receiver, JSMap::kTableOffset)));
        Label loop(this, { &var_index, &var_table }), done_loop(this);
        Goto(&loop);
        BIND(&loop);
        {
            // Transition {table} and {index} if there was any modification to
            // the {receiver} while we're iterating.
            TNode<IntPtrT> index = var_index.value();
            TNode<OrderedHashMap> table = var_table.value();
            std::tie(table, index) = Transition<OrderedHashMap>(table, index, [](Node*, Node*) {});

            // Read the next entry from the {table}, skipping holes.
            TNode<Object> entry_key;
            TNode<IntPtrT> entry_start_position;
            std::tie(entry_key, entry_start_position, index) = NextSkipHoles<OrderedHashMap>(table, index, &done_loop);

            // Load the entry value as well.
            Node* entry_value = LoadFixedArrayElement(
                table, entry_start_position,
                (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) * kTaggedSize);

            // Invoke the {callback} passing the {entry_key}, {entry_value} and the
            // {receiver}.
            CallJS(CodeFactory::Call(isolate()), context, callback, this_arg,
                entry_value, entry_key, receiver);

            // Continue with the next entry.
            var_index = index;
            var_table = table;
            Goto(&loop);
        }

        BIND(&done_loop);
        args.PopAndReturn(UndefinedConstant());

        BIND(&callback_not_callable);
        {
            CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
            Unreachable();
        }
    }

    TF_BUILTIN(MapPrototypeKeys, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);
        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.keys");
        Return(AllocateJSCollectionIterator<JSMapIterator>(
            context, Context::MAP_KEY_ITERATOR_MAP_INDEX, receiver));
    }

    TF_BUILTIN(MapPrototypeValues, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);
        ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
            "Map.prototype.values");
        Return(AllocateJSCollectionIterator<JSMapIterator>(
            context, Context::MAP_VALUE_ITERATOR_MAP_INDEX, receiver));
    }

    TF_BUILTIN(MapIteratorPrototypeNext, CollectionsBuiltinsAssembler)
    {
        const char* const kMethodName = "Map Iterator.prototype.next";
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);

        // Ensure that the {receiver} is actually a JSMapIterator.
        Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
        GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
        Node* const receiver_instance_type = LoadInstanceType(receiver);
        GotoIf(
            InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_VALUE_ITERATOR_TYPE),
            &if_receiver_valid);
        GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
            &if_receiver_valid);
        Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
            &if_receiver_valid, &if_receiver_invalid);
        BIND(&if_receiver_invalid);
        ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
            StringConstant(kMethodName), receiver);
        BIND(&if_receiver_valid);

        // Check if the {receiver} is exhausted.
        VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
        VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
        Label return_value(this, { &var_done, &var_value }), return_entry(this),
            return_end(this, Label::kDeferred);

        // Transition the {receiver} table if necessary.
        TNode<OrderedHashMap> table;
        TNode<IntPtrT> index;
        std::tie(table, index) = TransitionAndUpdate<JSMapIterator, OrderedHashMap>(CAST(receiver));

        // Read the next entry from the {table}, skipping holes.
        TNode<Object> entry_key;
        TNode<IntPtrT> entry_start_position;
        std::tie(entry_key, entry_start_position, index) = NextSkipHoles<OrderedHashMap>(table, index, &return_end);
        StoreObjectFieldNoWriteBarrier(receiver, JSMapIterator::kIndexOffset,
            SmiTag(index));
        var_value.Bind(entry_key);
        var_done.Bind(FalseConstant());

        // Check how to return the {key} (depending on {receiver} type).
        GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
            &return_value);
        var_value.Bind(LoadFixedArrayElement(
            table, entry_start_position,
            (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) * kTaggedSize));
        Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
            &return_value, &return_entry);

        BIND(&return_entry);
        {
            Node* result = AllocateJSIteratorResultForEntry(context, entry_key, var_value.value());
            Return(result);
        }

        BIND(&return_value);
        {
            Node* result = AllocateJSIteratorResult(context, var_value.value(), var_done.value());
            Return(result);
        }

        BIND(&return_end);
        {
            StoreObjectFieldRoot(receiver, JSMapIterator::kTableOffset,
                RootIndex::kEmptyOrderedHashMap);
            Goto(&return_value);
        }
    }

    TF_BUILTIN(SetPrototypeHas, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has");

        Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

        VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
            IntPtrConstant(0));
        VARIABLE(result, MachineRepresentation::kTaggedSigned, IntPtrConstant(0));
        Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
            if_key_bigint(this), entry_found(this), not_found(this), done(this);

        GotoIf(TaggedIsSmi(key), &if_key_smi);

        Node* key_map = LoadMap(key);
        Node* key_instance_type = LoadMapInstanceType(key_map);

        GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
        GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
        GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);

        FindOrderedHashTableEntryForOtherKey<OrderedHashSet>(
            context, table, key, &entry_start_position, &entry_found, &not_found);

        BIND(&if_key_smi);
        {
            FindOrderedHashTableEntryForSmiKey<OrderedHashSet>(
                table, key, &entry_start_position, &entry_found, &not_found);
        }

        BIND(&if_key_string);
        {
            FindOrderedHashTableEntryForStringKey<OrderedHashSet>(
                context, table, key, &entry_start_position, &entry_found, &not_found);
        }

        BIND(&if_key_heap_number);
        {
            FindOrderedHashTableEntryForHeapNumberKey<OrderedHashSet>(
                context, table, key, &entry_start_position, &entry_found, &not_found);
        }

        BIND(&if_key_bigint);
        {
            FindOrderedHashTableEntryForBigIntKey<OrderedHashSet>(
                context, table, key, &entry_start_position, &entry_found, &not_found);
        }

        BIND(&entry_found);
        Return(TrueConstant());

        BIND(&not_found);
        Return(FalseConstant());
    }

    TF_BUILTIN(SetPrototypeEntries, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);
        ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
            "Set.prototype.entries");
        Return(AllocateJSCollectionIterator<JSSetIterator>(
            context, Context::SET_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
    }

    TF_BUILTIN(SetPrototypeGetSize, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);
        ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
            "get Set.prototype.size");
        Node* const table = LoadObjectField(receiver, JSSet::kTableOffset);
        Return(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset()));
    }

    TF_BUILTIN(SetPrototypeForEach, CollectionsBuiltinsAssembler)
    {
        const char* const kMethodName = "Set.prototype.forEach";
        Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
        Node* const context = Parameter(Descriptor::kContext);
        CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
        Node* const receiver = args.GetReceiver();
        Node* const callback = args.GetOptionalArgumentValue(0);
        Node* const this_arg = args.GetOptionalArgumentValue(1);

        ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, kMethodName);

        // Ensure that {callback} is actually callable.
        Label callback_not_callable(this, Label::kDeferred);
        GotoIf(TaggedIsSmi(callback), &callback_not_callable);
        GotoIfNot(IsCallable(callback), &callback_not_callable);

        TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
        TVARIABLE(OrderedHashSet, var_table,
            CAST(LoadObjectField(receiver, JSSet::kTableOffset)));
        Label loop(this, { &var_index, &var_table }), done_loop(this);
        Goto(&loop);
        BIND(&loop);
        {
            // Transition {table} and {index} if there was any modification to
            // the {receiver} while we're iterating.
            TNode<IntPtrT> index = var_index.value();
            TNode<OrderedHashSet> table = var_table.value();
            std::tie(table, index) = Transition<OrderedHashSet>(table, index, [](Node*, Node*) {});

            // Read the next entry from the {table}, skipping holes.
            Node* entry_key;
            Node* entry_start_position;
            std::tie(entry_key, entry_start_position, index) = NextSkipHoles<OrderedHashSet>(table, index, &done_loop);

            // Invoke the {callback} passing the {entry_key} (twice) and the {receiver}.
            CallJS(CodeFactory::Call(isolate()), context, callback, this_arg, entry_key,
                entry_key, receiver);

            // Continue with the next entry.
            var_index = index;
            var_table = table;
            Goto(&loop);
        }

        BIND(&done_loop);
        args.PopAndReturn(UndefinedConstant());

        BIND(&callback_not_callable);
        {
            CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
            Unreachable();
        }
    }

    TF_BUILTIN(SetPrototypeValues, CollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);
        ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
            "Set.prototype.values");
        Return(AllocateJSCollectionIterator<JSSetIterator>(
            context, Context::SET_VALUE_ITERATOR_MAP_INDEX, receiver));
    }

    TF_BUILTIN(SetIteratorPrototypeNext, CollectionsBuiltinsAssembler)
    {
        const char* const kMethodName = "Set Iterator.prototype.next";
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const context = Parameter(Descriptor::kContext);

        // Ensure that the {receiver} is actually a JSSetIterator.
        Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
        GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
        Node* const receiver_instance_type = LoadInstanceType(receiver);
        GotoIf(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
            &if_receiver_valid);
        Branch(
            InstanceTypeEqual(receiver_instance_type, JS_SET_KEY_VALUE_ITERATOR_TYPE),
            &if_receiver_valid, &if_receiver_invalid);
        BIND(&if_receiver_invalid);
        ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
            StringConstant(kMethodName), receiver);
        BIND(&if_receiver_valid);

        // Check if the {receiver} is exhausted.
        VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
        VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
        Label return_value(this, { &var_done, &var_value }), return_entry(this),
            return_end(this, Label::kDeferred);

        // Transition the {receiver} table if necessary.
        TNode<OrderedHashSet> table;
        TNode<IntPtrT> index;
        std::tie(table, index) = TransitionAndUpdate<JSSetIterator, OrderedHashSet>(CAST(receiver));

        // Read the next entry from the {table}, skipping holes.
        Node* entry_key;
        Node* entry_start_position;
        std::tie(entry_key, entry_start_position, index) = NextSkipHoles<OrderedHashSet>(table, index, &return_end);
        StoreObjectFieldNoWriteBarrier(receiver, JSSetIterator::kIndexOffset,
            SmiTag(index));
        var_value.Bind(entry_key);
        var_done.Bind(FalseConstant());

        // Check how to return the {key} (depending on {receiver} type).
        Branch(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
            &return_value, &return_entry);

        BIND(&return_entry);
        {
            Node* result = AllocateJSIteratorResultForEntry(context, var_value.value(),
                var_value.value());
            Return(result);
        }

        BIND(&return_value);
        {
            Node* result = AllocateJSIteratorResult(context, var_value.value(), var_done.value());
            Return(result);
        }

        BIND(&return_end);
        {
            StoreObjectFieldRoot(receiver, JSSetIterator::kTableOffset,
                RootIndex::kEmptyOrderedHashSet);
            Goto(&return_value);
        }
    }

    template <typename CollectionType>
    void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex(
        Node* const table, Node* const key, Node* const context, Variable* result,
        Label* if_entry_found, Label* if_not_found)
    {
        Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
            if_key_bigint(this);

        GotoIf(TaggedIsSmi(key), &if_key_smi);

        Node* key_map = LoadMap(key);
        Node* key_instance_type = LoadMapInstanceType(key_map);

        GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
        GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
        GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);

        FindOrderedHashTableEntryForOtherKey<CollectionType>(
            context, table, key, result, if_entry_found, if_not_found);

        BIND(&if_key_smi);
        {
            FindOrderedHashTableEntryForSmiKey<CollectionType>(
                table, key, result, if_entry_found, if_not_found);
        }

        BIND(&if_key_string);
        {
            FindOrderedHashTableEntryForStringKey<CollectionType>(
                context, table, key, result, if_entry_found, if_not_found);
        }

        BIND(&if_key_heap_number);
        {
            FindOrderedHashTableEntryForHeapNumberKey<CollectionType>(
                context, table, key, result, if_entry_found, if_not_found);
        }

        BIND(&if_key_bigint);
        {
            FindOrderedHashTableEntryForBigIntKey<CollectionType>(
                context, table, key, result, if_entry_found, if_not_found);
        }
    }

    TF_BUILTIN(FindOrderedHashMapEntry, CollectionsBuiltinsAssembler)
    {
        Node* const table = Parameter(Descriptor::kTable);
        Node* const key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
            IntPtrConstant(0));
        Label entry_found(this), not_found(this);

        TryLookupOrderedHashTableIndex<OrderedHashMap>(
            table, key, context, &entry_start_position, &entry_found, &not_found);

        BIND(&entry_found);
        Return(SmiTag(entry_start_position.value()));

        BIND(&not_found);
        Return(SmiConstant(-1));
    }

    class WeakCollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
    public:
        explicit WeakCollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
            : BaseCollectionsAssembler(state)
        {
        }

    protected:
        void AddEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
            TNode<Object> key, TNode<Object> value,
            TNode<IntPtrT> number_of_elements);

        TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
            TNode<IntPtrT> at_least_space_for) override;

        // Generates and sets the identity for a JSRececiver.
        TNode<Smi> CreateIdentityHash(TNode<Object> receiver);
        TNode<IntPtrT> EntryMask(TNode<IntPtrT> capacity);

        // Builds code that finds the EphemeronHashTable entry for a {key} using the
        // comparison code generated by {key_compare}. The key index is returned if
        // the {key} is found.
        typedef std::function<void(TNode<Object> entry_key, Label* if_same)>
            KeyComparator;
        TNode<IntPtrT> FindKeyIndex(TNode<HeapObject> table, TNode<IntPtrT> key_hash,
            TNode<IntPtrT> entry_mask,
            const KeyComparator& key_compare);

        // Builds code that finds an EphemeronHashTable entry available for a new
        // entry.
        TNode<IntPtrT> FindKeyIndexForInsertion(TNode<HeapObject> table,
            TNode<IntPtrT> key_hash,
            TNode<IntPtrT> entry_mask);

        // Builds code that finds the EphemeronHashTable entry with key that matches
        // {key} and returns the entry's key index. If {key} cannot be found, jumps to
        // {if_not_found}.
        TNode<IntPtrT> FindKeyIndexForKey(TNode<HeapObject> table, TNode<Object> key,
            TNode<IntPtrT> hash,
            TNode<IntPtrT> entry_mask,
            Label* if_not_found);

        TNode<Word32T> InsufficientCapacityToAdd(TNode<IntPtrT> capacity,
            TNode<IntPtrT> number_of_elements,
            TNode<IntPtrT> number_of_deleted);
        TNode<IntPtrT> KeyIndexFromEntry(TNode<IntPtrT> entry);

        TNode<IntPtrT> LoadNumberOfElements(TNode<EphemeronHashTable> table,
            int offset);
        TNode<IntPtrT> LoadNumberOfDeleted(TNode<EphemeronHashTable> table,
            int offset = 0);
        TNode<EphemeronHashTable> LoadTable(TNode<JSWeakCollection> collection);
        TNode<IntPtrT> LoadTableCapacity(TNode<EphemeronHashTable> table);

        void RemoveEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
            TNode<IntPtrT> number_of_elements);
        TNode<BoolT> ShouldRehash(TNode<IntPtrT> number_of_elements,
            TNode<IntPtrT> number_of_deleted);
        TNode<Word32T> ShouldShrink(TNode<IntPtrT> capacity,
            TNode<IntPtrT> number_of_elements);
        TNode<IntPtrT> ValueIndexFromKeyIndex(TNode<IntPtrT> key_index);
    };

    void WeakCollectionsBuiltinsAssembler::AddEntry(
        TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
        TNode<Object> key, TNode<Object> value, TNode<IntPtrT> number_of_elements)
    {
        // See EphemeronHashTable::AddEntry().
        TNode<IntPtrT> value_index = ValueIndexFromKeyIndex(key_index);
        UnsafeStoreFixedArrayElement(table, key_index, key,
            UPDATE_EPHEMERON_KEY_WRITE_BARRIER);
        UnsafeStoreFixedArrayElement(table, value_index, value);

        // See HashTableBase::ElementAdded().
        UnsafeStoreFixedArrayElement(
            table, EphemeronHashTable::kNumberOfElementsIndex,
            SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
    }

    TNode<Object> WeakCollectionsBuiltinsAssembler::AllocateTable(
        Variant variant, TNode<Context> context,
        TNode<IntPtrT> at_least_space_for)
    {
        // See HashTable::New().
        CSA_ASSERT(this,
            IntPtrLessThanOrEqual(IntPtrConstant(0), at_least_space_for));
        TNode<IntPtrT> capacity = HashTableComputeCapacity(at_least_space_for);

        // See HashTable::NewInternal().
        TNode<IntPtrT> length = KeyIndexFromEntry(capacity);
        TNode<FixedArray> table = CAST(
            AllocateFixedArray(HOLEY_ELEMENTS, length, kAllowLargeObjectAllocation));

        RootIndex map_root_index = EphemeronHashTableShape::GetMapRootIndex();
        StoreMapNoWriteBarrier(table, map_root_index);
        StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
            SmiConstant(0), SKIP_WRITE_BARRIER);
        StoreFixedArrayElement(table,
            EphemeronHashTable::kNumberOfDeletedElementsIndex,
            SmiConstant(0), SKIP_WRITE_BARRIER);
        StoreFixedArrayElement(table, EphemeronHashTable::kCapacityIndex,
            SmiFromIntPtr(capacity), SKIP_WRITE_BARRIER);

        TNode<IntPtrT> start = KeyIndexFromEntry(IntPtrConstant(0));
        FillFixedArrayWithValue(HOLEY_ELEMENTS, table, start, length,
            RootIndex::kUndefinedValue);
        return table;
    }

    TNode<Smi> WeakCollectionsBuiltinsAssembler::CreateIdentityHash(
        TNode<Object> key)
    {
        TNode<ExternalReference> function_addr = ExternalConstant(ExternalReference::jsreceiver_create_identity_hash());
        TNode<ExternalReference> isolate_ptr = ExternalConstant(ExternalReference::isolate_address(isolate()));

        MachineType type_ptr = MachineType::Pointer();
        MachineType type_tagged = MachineType::AnyTagged();

        return CAST(CallCFunction(function_addr, type_tagged,
            std::make_pair(type_ptr, isolate_ptr),
            std::make_pair(type_tagged, key)));
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::EntryMask(
        TNode<IntPtrT> capacity)
    {
        return IntPtrSub(capacity, IntPtrConstant(1));
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndex(
        TNode<HeapObject> table, TNode<IntPtrT> key_hash, TNode<IntPtrT> entry_mask,
        const KeyComparator& key_compare)
    {
        // See HashTable::FirstProbe().
        TVARIABLE(IntPtrT, var_entry, WordAnd(key_hash, entry_mask));
        TVARIABLE(IntPtrT, var_count, IntPtrConstant(0));

        Variable* loop_vars[] = { &var_count, &var_entry };
        Label loop(this, arraysize(loop_vars), loop_vars), if_found(this);
        Goto(&loop);
        BIND(&loop);
        TNode<IntPtrT> key_index;
        {
            key_index = KeyIndexFromEntry(var_entry.value());
            TNode<Object> entry_key = UnsafeLoadFixedArrayElement(CAST(table), key_index);

            key_compare(entry_key, &if_found);

            // See HashTable::NextProbe().
            Increment(&var_count);
            var_entry = WordAnd(IntPtrAdd(var_entry.value(), var_count.value()), entry_mask);
            Goto(&loop);
        }

        BIND(&if_found);
        return key_index;
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndexForInsertion(
        TNode<HeapObject> table, TNode<IntPtrT> key_hash,
        TNode<IntPtrT> entry_mask)
    {
        // See HashTable::FindInsertionEntry().
        auto is_not_live = [&](TNode<Object> entry_key, Label* if_found) {
            // This is the the negative form BaseShape::IsLive().
            GotoIf(Word32Or(IsTheHole(entry_key), IsUndefined(entry_key)), if_found);
        };
        return FindKeyIndex(table, key_hash, entry_mask, is_not_live);
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndexForKey(
        TNode<HeapObject> table, TNode<Object> key, TNode<IntPtrT> hash,
        TNode<IntPtrT> entry_mask, Label* if_not_found)
    {
        // See HashTable::FindEntry().
        auto match_key_or_exit_on_empty = [&](TNode<Object> entry_key,
                                              Label* if_same) {
            GotoIf(IsUndefined(entry_key), if_not_found);
            GotoIf(WordEqual(entry_key, key), if_same);
        };
        return FindKeyIndex(table, hash, entry_mask, match_key_or_exit_on_empty);
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::KeyIndexFromEntry(
        TNode<IntPtrT> entry)
    {
        // See HashTable::KeyAt().
        // (entry * kEntrySize) + kElementsStartIndex + kEntryKeyIndex
        return IntPtrAdd(
            IntPtrMul(entry, IntPtrConstant(EphemeronHashTable::kEntrySize)),
            IntPtrConstant(EphemeronHashTable::kElementsStartIndex + EphemeronHashTable::kEntryKeyIndex));
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfElements(
        TNode<EphemeronHashTable> table, int offset)
    {
        TNode<IntPtrT> number_of_elements = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
            table, EphemeronHashTable::kNumberOfElementsIndex)));
        return IntPtrAdd(number_of_elements, IntPtrConstant(offset));
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfDeleted(
        TNode<EphemeronHashTable> table, int offset)
    {
        TNode<IntPtrT> number_of_deleted = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
            table, EphemeronHashTable::kNumberOfDeletedElementsIndex)));
        return IntPtrAdd(number_of_deleted, IntPtrConstant(offset));
    }

    TNode<EphemeronHashTable> WeakCollectionsBuiltinsAssembler::LoadTable(
        TNode<JSWeakCollection> collection)
    {
        return CAST(LoadObjectField(collection, JSWeakCollection::kTableOffset));
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadTableCapacity(
        TNode<EphemeronHashTable> table)
    {
        return SmiUntag(CAST(
            UnsafeLoadFixedArrayElement(table, EphemeronHashTable::kCapacityIndex)));
    }

    TNode<Word32T> WeakCollectionsBuiltinsAssembler::InsufficientCapacityToAdd(
        TNode<IntPtrT> capacity, TNode<IntPtrT> number_of_elements,
        TNode<IntPtrT> number_of_deleted)
    {
        // This is the negative form of HashTable::HasSufficientCapacityToAdd().
        // Return true if:
        //   - more than 50% of the available space are deleted elements
        //   - less than 50% will be available
        TNode<IntPtrT> available = IntPtrSub(capacity, number_of_elements);
        TNode<IntPtrT> half_available = WordShr(available, 1);
        TNode<IntPtrT> needed_available = WordShr(number_of_elements, 1);
        return Word32Or(
            // deleted > half
            IntPtrGreaterThan(number_of_deleted, half_available),
            // elements + needed available > capacity
            IntPtrGreaterThan(IntPtrAdd(number_of_elements, needed_available),
                capacity));
    }

    void WeakCollectionsBuiltinsAssembler::RemoveEntry(
        TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
        TNode<IntPtrT> number_of_elements)
    {
        // See EphemeronHashTable::RemoveEntry().
        TNode<IntPtrT> value_index = ValueIndexFromKeyIndex(key_index);
        StoreFixedArrayElement(table, key_index, TheHoleConstant());
        StoreFixedArrayElement(table, value_index, TheHoleConstant());

        // See HashTableBase::ElementRemoved().
        TNode<IntPtrT> number_of_deleted = LoadNumberOfDeleted(table, 1);
        StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
            SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
        StoreFixedArrayElement(table,
            EphemeronHashTable::kNumberOfDeletedElementsIndex,
            SmiFromIntPtr(number_of_deleted), SKIP_WRITE_BARRIER);
    }

    TNode<BoolT> WeakCollectionsBuiltinsAssembler::ShouldRehash(
        TNode<IntPtrT> number_of_elements, TNode<IntPtrT> number_of_deleted)
    {
        // Rehash if more than 33% of the entries are deleted.
        return IntPtrGreaterThanOrEqual(WordShl(number_of_deleted, 1),
            number_of_elements);
    }

    TNode<Word32T> WeakCollectionsBuiltinsAssembler::ShouldShrink(
        TNode<IntPtrT> capacity, TNode<IntPtrT> number_of_elements)
    {
        // See HashTable::Shrink().
        TNode<IntPtrT> quarter_capacity = WordShr(capacity, 2);
        return Word32And(
            // Shrink to fit the number of elements if only a quarter of the
            // capacity is filled with elements.
            IntPtrLessThanOrEqual(number_of_elements, quarter_capacity),

            // Allocate a new dictionary with room for at least the current
            // number of elements. The allocation method will make sure that
            // there is extra room in the dictionary for additions. Don't go
            // lower than room for 16 elements.
            IntPtrGreaterThanOrEqual(number_of_elements, IntPtrConstant(16)));
    }

    TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::ValueIndexFromKeyIndex(
        TNode<IntPtrT> key_index)
    {
        return IntPtrAdd(key_index,
            IntPtrConstant(EphemeronHashTableShape::kEntryValueIndex - EphemeronHashTable::kEntryKeyIndex));
    }

    TF_BUILTIN(WeakMapConstructor, WeakCollectionsBuiltinsAssembler)
    {
        TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
        TNode<IntPtrT> argc = ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));

        GenerateConstructor(kWeakMap, isolate()->factory()->WeakMap_string(),
            new_target, argc, context);
    }

    TF_BUILTIN(WeakSetConstructor, WeakCollectionsBuiltinsAssembler)
    {
        TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
        TNode<IntPtrT> argc = ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));

        GenerateConstructor(kWeakSet, isolate()->factory()->WeakSet_string(),
            new_target, argc, context);
    }

    TF_BUILTIN(WeakMapLookupHashIndex, WeakCollectionsBuiltinsAssembler)
    {
        TNode<EphemeronHashTable> table = CAST(Parameter(Descriptor::kTable));
        TNode<Object> key = CAST(Parameter(Descriptor::kKey));

        Label if_not_found(this);

        GotoIfNotJSReceiver(key, &if_not_found);

        TNode<IntPtrT> hash = LoadJSReceiverIdentityHash(key, &if_not_found);
        TNode<IntPtrT> capacity = LoadTableCapacity(table);
        TNode<IntPtrT> key_index = FindKeyIndexForKey(table, key, hash, EntryMask(capacity), &if_not_found);
        Return(SmiTag(ValueIndexFromKeyIndex(key_index)));

        BIND(&if_not_found);
        Return(SmiConstant(-1));
    }

    TF_BUILTIN(WeakMapGet, WeakCollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        Label return_undefined(this);

        ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
            "WeakMap.prototype.get");

        TNode<EphemeronHashTable> const table = LoadTable(CAST(receiver));
        TNode<Smi> const index = CAST(CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key));

        GotoIf(WordEqual(index, SmiConstant(-1)), &return_undefined);

        Return(LoadFixedArrayElement(table, SmiUntag(index)));

        BIND(&return_undefined);
        Return(UndefinedConstant());
    }

    TF_BUILTIN(WeakMapPrototypeHas, WeakCollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        Label return_false(this);

        ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
            "WeakMap.prototype.has");

        TNode<EphemeronHashTable> const table = LoadTable(CAST(receiver));
        Node* const index = CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

        GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);

        Return(TrueConstant());

        BIND(&return_false);
        Return(FalseConstant());
    }

    // Helper that removes the entry with a given key from the backing store
    // (EphemeronHashTable) of a WeakMap or WeakSet.
    TF_BUILTIN(WeakCollectionDelete, WeakCollectionsBuiltinsAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<JSWeakCollection> collection = CAST(Parameter(Descriptor::kCollection));
        TNode<Object> key = CAST(Parameter(Descriptor::kKey));

        Label call_runtime(this), if_not_found(this);

        GotoIfNotJSReceiver(key, &if_not_found);

        TNode<IntPtrT> hash = LoadJSReceiverIdentityHash(key, &if_not_found);
        TNode<EphemeronHashTable> table = LoadTable(collection);
        TNode<IntPtrT> capacity = LoadTableCapacity(table);
        TNode<IntPtrT> key_index = FindKeyIndexForKey(table, key, hash, EntryMask(capacity), &if_not_found);
        TNode<IntPtrT> number_of_elements = LoadNumberOfElements(table, -1);
        GotoIf(ShouldShrink(capacity, number_of_elements), &call_runtime);

        RemoveEntry(table, key_index, number_of_elements);
        Return(TrueConstant());

        BIND(&if_not_found);
        Return(FalseConstant());

        BIND(&call_runtime);
        Return(CallRuntime(Runtime::kWeakCollectionDelete, context, collection, key,
            SmiTag(hash)));
    }

    // Helper that sets the key and value to the backing store (EphemeronHashTable)
    // of a WeakMap or WeakSet.
    TF_BUILTIN(WeakCollectionSet, WeakCollectionsBuiltinsAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<JSWeakCollection> collection = CAST(Parameter(Descriptor::kCollection));
        TNode<JSReceiver> key = CAST(Parameter(Descriptor::kKey));
        TNode<Object> value = CAST(Parameter(Descriptor::kValue));

        CSA_ASSERT(this, IsJSReceiver(key));

        Label call_runtime(this), if_no_hash(this), if_not_found(this);

        TNode<EphemeronHashTable> table = LoadTable(collection);
        TNode<IntPtrT> capacity = LoadTableCapacity(table);
        TNode<IntPtrT> entry_mask = EntryMask(capacity);

        TVARIABLE(IntPtrT, var_hash, LoadJSReceiverIdentityHash(key, &if_no_hash));
        TNode<IntPtrT> key_index = FindKeyIndexForKey(table, key, var_hash.value(),
            entry_mask, &if_not_found);

        StoreFixedArrayElement(table, ValueIndexFromKeyIndex(key_index), value);
        Return(collection);

        BIND(&if_no_hash);
        {
            var_hash = SmiUntag(CreateIdentityHash(key));
            Goto(&if_not_found);
        }
        BIND(&if_not_found);
        {
            TNode<IntPtrT> number_of_deleted = LoadNumberOfDeleted(table);
            TNode<IntPtrT> number_of_elements = LoadNumberOfElements(table, 1);

            // TODO(pwong): Port HashTable's Rehash() and EnsureCapacity() to CSA.
            GotoIf(Word32Or(ShouldRehash(number_of_elements, number_of_deleted),
                       InsufficientCapacityToAdd(capacity, number_of_elements,
                           number_of_deleted)),
                &call_runtime);

            TNode<IntPtrT> insertion_key_index = FindKeyIndexForInsertion(table, var_hash.value(), entry_mask);
            AddEntry(table, insertion_key_index, key, value, number_of_elements);
            Return(collection);
        }
        BIND(&call_runtime);
        {
            CallRuntime(Runtime::kWeakCollectionSet, context, collection, key, value,
                SmiTag(var_hash.value()));
            Return(collection);
        }
    }

    TF_BUILTIN(WeakMapPrototypeDelete, CodeStubAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
        TNode<Object> key = CAST(Parameter(Descriptor::kKey));

        ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
            "WeakMap.prototype.delete");

        Return(CallBuiltin(Builtins::kWeakCollectionDelete, context, receiver, key));
    }

    TF_BUILTIN(WeakMapPrototypeSet, WeakCollectionsBuiltinsAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
        TNode<Object> key = CAST(Parameter(Descriptor::kKey));
        TNode<Object> value = CAST(Parameter(Descriptor::kValue));

        ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
            "WeakMap.prototype.set");

        Label throw_invalid_key(this);
        GotoIfNotJSReceiver(key, &throw_invalid_key);

        Return(
            CallBuiltin(Builtins::kWeakCollectionSet, context, receiver, key, value));

        BIND(&throw_invalid_key);
        ThrowTypeError(context, MessageTemplate::kInvalidWeakMapKey, key);
    }

    TF_BUILTIN(WeakSetPrototypeAdd, WeakCollectionsBuiltinsAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
        TNode<Object> value = CAST(Parameter(Descriptor::kValue));

        ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
            "WeakSet.prototype.add");

        Label throw_invalid_value(this);
        GotoIfNotJSReceiver(value, &throw_invalid_value);

        Return(CallBuiltin(Builtins::kWeakCollectionSet, context, receiver, value,
            TrueConstant()));

        BIND(&throw_invalid_value);
        ThrowTypeError(context, MessageTemplate::kInvalidWeakSetValue, value);
    }

    TF_BUILTIN(WeakSetPrototypeDelete, CodeStubAssembler)
    {
        TNode<Context> context = CAST(Parameter(Descriptor::kContext));
        TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
        TNode<Object> value = CAST(Parameter(Descriptor::kValue));

        ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
            "WeakSet.prototype.delete");

        Return(
            CallBuiltin(Builtins::kWeakCollectionDelete, context, receiver, value));
    }

    TF_BUILTIN(WeakSetPrototypeHas, WeakCollectionsBuiltinsAssembler)
    {
        Node* const receiver = Parameter(Descriptor::kReceiver);
        Node* const key = Parameter(Descriptor::kKey);
        Node* const context = Parameter(Descriptor::kContext);

        Label return_false(this);

        ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
            "WeakSet.prototype.has");

        Node* const table = LoadTable(CAST(receiver));
        Node* const index = CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

        GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);

        Return(TrueConstant());

        BIND(&return_false);
        Return(FalseConstant());
    }

} // namespace internal
} // namespace v8
